带一些条件的随机列表

`List<int> list1 = new List<int>{0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10};`

`List<int> list2 = new List<int> {0,1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,10};`

List<int> list3 = new List<int>(){0,1,1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,8,8,8,9,9,9,9,10,10};

优化版

令我失望的是，我优化的函数只比LINQ的"直接"版本快7倍。未优化LINQ 1m43s优化14.7s.

32位linux
• Mono 2.11 (c# 4.0)编译器与-optimize+，
• 1,000,000 TESTITERATIONS
VERBOSE not #define -d

已优化的内容:

• 假定输入和输出为数组
• 在输入数组上工作
• "手动"分析相同值的运行，而不是使用GroupBy(使用ValueRun struct)
• 有这些ValueRun结构在数组中而不是Enumerable (List);排序/洗牌就地
• 使用unsafe块和指针(没有明显的区别…)
• 使用模索引代替MAGIC Linq代码
• 通过迭代追加而不是嵌套LINQ生成输出。这可能是最有效的。实际上，如果我们能够将ValueRun的国家集合按这个计数进行排序，那就更好了，这似乎很容易做到;然而，转置索引(循环约束所需要的)使事情变得复杂。无论如何，应用这种优化的收益将随着更大的输入和许多唯一值以及一些高度重复的值而更大。

这是优化版本的代码。_通过移除rng的播种可以获得额外的速度增益;这些只是为了能够对输出进行回归测试。

[... old code removed as well ...]

---

原响应(部分)

如果我理解对了，你是在尝试设计一个洗牌，以防止重复元素在输出中连续出现(至少有2个元素的交错)。

这在一般情况下是不可解的。假设输入只有相同的元素:)

更新:乱世

就像我在笔记中提到的，我觉得我一直都没有走在正确的轨道上。要么我应该调用图论(有人吗?)，要么使用简单的"蛮力"算法，这是Erick的建议。

无论如何，这样你就可以看到我一直在做什么，也可以看到问题是什么(使随机样本快速看到问题):

#define OUTPUT       // to display the testcase results
#define VERIFY       // to selfcheck internals and verify results
#define SIMPLERANDOM
// #define DEBUG        // to really traces the internals
using System;
using System.Linq;
using System.Collections.Generic;
public static class Q5899274
{
    // TEST DRIVER CODE
    private const int TESTITERATIONS = 100000;
    public static int Main(string[] args)
    {
        var testcases = new [] {
            new [] {0,1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,10},
            new [] {0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10},
            new [] { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41, 42, 42, 42, },
            new [] {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
        }.AsEnumerable();
        // // creating some very random testcases
        // testcases = Enumerable.Range(0, 10000).Select(nr => Enumerable.Range(GROUPWIDTH, _seeder.Next(GROUPWIDTH, 400)).Select(el => _seeder.Next(-40, 40)).ToArray());
        foreach (var testcase in testcases)
        {
            // _seeder = new Random(45); for (int i=0; i<TESTITERATIONS; i++) // for benchmarking/regression
            {
                try
                {
                    var output = TestOptimized(testcase);
#if OUTPUT
                    Console.WriteLine("spread't{0}", string.Join(", ", output));
#endif
#if VERIFY
                    AssertValidOutput(output);
#endif
                } catch(Exception e)
                {
                    Console.Error.WriteLine("Exception for input {0}:", string.Join(", ", testcase));
                    Console.Error.WriteLine("Sequence length {0}: {1} groups and remainder {2}", testcase.Count(), (testcase.Count()+GROUPWIDTH-1)/GROUPWIDTH, testcase.Count() % GROUPWIDTH);
                    Console.Error.WriteLine("Analysis: 'n't{0}", string.Join("'n't", InternalAnalyzeInputRuns(testcase)));
                    Console.Error.WriteLine(e);
                }
            }
        }
        return 0;
    }
#region Algorithm Core
    const int GROUPWIDTH = 3; /* implying a minimum distance of 2
                                 (GROUPWIDTH-1) values in between duplicates
                                 must be guaranteed*/
    public static T[] TestOptimized<T>(T[] input, bool doShuffle = false)
        where T: IComparable<T>
    {
        if (input.Length==0)
            return input;
        var runs = InternalAnalyzeInputRuns(input);
#if VERIFY
        CanBeSatisfied(input.Length, runs); // throws NoValidOrderingExists if not
#endif
        var transpositions = CreateTranspositionIndex(input.Length, runs);
        int pos = 0;
        for (int run=0; run<runs.Length; run++)
            for (int i=0; i<runs[run].runlength; i++)
                input[transpositions[pos++]] = runs[run].value;
        return input;
    }
    private static ValueRun<T>[] InternalAnalyzeInputRuns<T>(T[] input)
    {
        var listOfRuns = new List<ValueRun<T>>();
        Array.Sort(input);
        ValueRun<T> current = new ValueRun<T> { value = input[0], runlength = 1 };
        for (int i=1; i<=input.Length; i++)
        {
            if (i<input.Length && input[i].Equals(current.value))
                current.runlength++;
            else
            {
                listOfRuns.Add(current);
                if (i<input.Length)
                    current = new ValueRun<T> { value = input[i], runlength = 1 };
            }
        }
#if SIMPLERANDOM
        var rng = new Random(_seeder.Next());
        listOfRuns.ForEach(run => run.tag = rng.Next()); // this shuffles them
#endif
        var runs = listOfRuns.ToArray();
        Array.Sort(runs);
        return runs;
    }
    // NOTE: suboptimal performance 
    //   * some steps can be done inline with CreateTranspositionIndex for
    //   efficiency
    private class NoValidOrderingExists : Exception { public NoValidOrderingExists(string message) : base(message) { } }
    private static bool CanBeSatisfied<T>(int length, ValueRun<T>[] runs)
    {
        int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
        int remainder = length % GROUPWIDTH;
        // elementary checks
        if (length<GROUPWIDTH)
            throw new NoValidOrderingExists(string.Format("Input sequence shorter ({0}) than single group of {1})", length, GROUPWIDTH));
        if (runs.Length<GROUPWIDTH)
            throw new NoValidOrderingExists(string.Format("Insufficient distinct values ({0}) in input sequence to fill a single group of {1})", runs.Length, GROUPWIDTH));
        int effectivewidth = Math.Min(GROUPWIDTH, length);
        // check for a direct exhaustion by repeating a single value more than the available number of groups (for the relevant groupmember if there is a remainder group)
        for (int groupmember=0; groupmember<effectivewidth; groupmember++)
        {
            int capacity = remainder==0? groups : groups -1;
            if (capacity < runs[groupmember].runlength)
                throw new NoValidOrderingExists(string.Format("Capacity exceeded on groupmember index {0} with capacity of {1} elements, (runlength {2} in run of '{3}'))",
                            groupmember, capacity, runs[groupmember].runlength, runs[groupmember].value));
        }
        // with the above, no single ValueRun should be a problem; however, due
        // to space exhaustion duplicates could end up being squeezed into the
        // 'remainder' group, which could be an incomplete group; 
        // In particular, if the smallest ValueRun (tail) has a runlength>1
        // _and_ there is an imcomplete remainder group, there is a problem
        if (runs.Last().runlength>1 && (0!=remainder))
            throw new NoValidOrderingExists("Smallest ValueRun would spill into trailing incomplete group");
        return true;
    }
    // will also verify solvability of input sequence
    private static int[] CreateTranspositionIndex<T>(int length, ValueRun<T>[] runs)
        where T: IComparable<T>
    {
        int remainder = length % GROUPWIDTH;
        int effectivewidth = Math.Min(GROUPWIDTH, length);
        var transpositions = new int[length];
        {
            int outit = 0;
            for (int groupmember=0; groupmember<effectivewidth; groupmember++)
                for (int pos=groupmember; outit<length && pos<(length-remainder) /* avoid the remainder */; pos+=GROUPWIDTH)
                    transpositions[outit++] = pos;
            while (outit<length)
            {
                transpositions[outit] = outit;
                outit += 1;
            }
#if DEBUG
            int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
            Console.WriteLine("Natural transpositions ({1} elements in {0} groups, remainder {2}): ", groups, length, remainder);
            Console.WriteLine("'t{0}", string.Join(" ", transpositions));
            var sum1 = string.Join(":", Enumerable.Range(0, length));
            var sum2 = string.Join(":", transpositions.OrderBy(i=>i));
            if (sum1!=sum2)
                throw new ArgumentException("transpositions do not cover range'n'tsum1 = " + sum1 + "'n'tsum2 = " + sum2);
#endif
        }
        return transpositions;
    }
#endregion // Algorithm Core
#region Utilities
    private struct ValueRun<T> : IComparable<ValueRun<T>>
    {
        public T value;
        public int runlength;
        public int tag;         // set to random for shuffling
        public int CompareTo(ValueRun<T> other) { var res = other.runlength.CompareTo(runlength); return 0==res? tag.CompareTo(other.tag) : res; }
        public override string ToString() { return string.Format("[{0}x {1}]", runlength, value); }
    }
    private static /*readonly*/ Random _seeder = new Random(45);
#endregion // Utilities
#region Error detection/verification
    public static void AssertValidOutput<T>(IEnumerable<T> output)
        where T:IComparable<T>
    {
        var repl = output.Concat(output.Take(GROUPWIDTH)).ToArray();
        for (int i=1; i<repl.Length; i++) 
            for (int j=Math.Max(0, i-(GROUPWIDTH-1)); j<i; j++)
                if (repl[i].Equals(repl[j]))
                    throw new ArgumentException(String.Format("Improper duplicate distance found: (#{0};#{1}) out of {2}: value is '{3}'", j, i, output.Count(), repl[j]));
    }
#endregion
}

您的需求消除了真正的洗牌选择:没有随机性，或者有受控的随机性。这里有一个特殊的方法

1. 对原始列表进行排序L
2. 查找模式M及其频率n
3. 如果n是偶数，则 n++。
4. 创建k (= 5* n - 1)列表(素数到n, 5乘以n) L ₁到L _k
   (选择5是为了避免两个前一个元素和两个后一个元素)
5. 以轮询方式将所有元素分配到k列表
6. 单独洗牌所有k列表。
7. 按以下顺序整理k清单内容:a.随机选择+5或-5作为x。
   b.选择一个随机数j .
   c.重复k次:
   i.添加L _j中的所有内容。
   2j <- (j + x) mod k

(5、6、7、7、8、8,9,10,12日,13日,13日,14日,14日,14日,17日,18日,18日,19日,19日,20日,21日,21日,21日,21日,24日,24日,26日,26日,26日,27日,27日,27日,29日,29日,30日,31日31日31日31日,32岁,32岁,32岁,33岁,35岁,35岁,37岁,38岁,39岁,40岁,42岁,43岁,44岁,44岁,46岁,46岁,47岁,48岁,50岁,50岁,50岁,50岁,51岁,52岁,53岁,54岁,55岁,56岁,57岁的57岁今年58岁,60岁,60岁,60岁,61,62,63,63,64,64,65,65,65,68,71,71,72,72,73,74,74,74,74,75,76,76,76,77,77,77,78,78,78,79,79,80,81,82,86,88,88,89,89,90,91,92,92,92,93,93,94,94,95,96,99,99,[100、102、102、103、103、105、106、106、107、108、113、115、116、118、119、123、124、125、127、127、127、128、131、133、133、134、135、135、137、137、138、139、141、143、143、143、145、146、147、153、156、157、158、160、164、166、170、173、175、181、181、184、185、187、188、190、200、200、215、217、234、238、240]

mode = 4，所以19个槽(#0 - #18)

0:[7, 21岁,32岁,50岁,65,77,93,115,137,173]
[8, 21, 33, 51, 65, 78, 93, 116, 137, 175]
[8, 24, 35, 52, 65, 78, 94, 118, 138, 181]
[3] [9,24, 35, 53, 68, 78, 94, 119, 139, 181]
[10, 26, 37, 54, 71, 79, 95, 123, 141, 184]
[12, 26, 38, 55, 71, 79, 96, 124, 143, 185]
[6] [13, 26, 39, 56, 72, 80, 99, 125, 143, 187]
[7] [13, 27, 40, 57, 72, 81, 99, 127, 143, 188]
[14, 27, 42, 57, 73, 82, 100, 127, 145, 190]
[14, 27, 43, 58, 74, 86, 102, 127, 146, 200]
[10] [14, 29, 44, 60, 74, 88, 102, 128, 147, 200]
[11] [17, 29, 44, 60, 74, 88, 103, 131, 153, 215]
[12] [18, 30, 46, 60, 74, 89, 103, 133, 156, 217]
13: [18, 31, 46, 61, 75, 89, 105, 133, 157, 234]
[19, 31, 47, 62, 76, 90, 106, 134, 158, 238]
[19, 31, 48, 63, 76, 91, 106, 135, 160, 240]
[16] [5,20, 31, 50, 63, 76, 92, 107, 135, 164]
[17] [6,21, 32, 50, 64, 77, 92, 108, 135, 166]
[7, 21, 32, 50, 64, 77, 92, 113, 137, 170]

洗牌单个列表，并间隔5个槽选择列表(从#16随机开始):

16:[31日135、92、76、107、5,164年,63年,20年,50]
[2] [52, 24, 35, 78, 181, 8, 138, 94, 118, 65]
[7] [57, 143, 99, 81, 40, 13, 127, 72, 188, 27]
[12] [46, 30, 60, 89, 133, 74, 156, 18, 103, 217]
[17] [64, 50, 135, 92, 21, 32, 108, 77, 166, 6]
[3] [9,94,181, 119, 24, 35, 139, 68, 53,78]
[8] [145, 27, 14, 57, 42, 100, 190, 82, 73, 127]
13: [89, 18, 75, 61, 157, 234, 133, 105, 31, 46]
18: [113, 21, 7, 92, 64, 32, 137, 50, 170, 77]
[4] [71, 10, 37, 26, 123, 54, 184, 79, 95, 141]
[27, 74, 86, 14, 102, 146, 127, 43, 58, 200]
[14] [62, 106, 158, 134, 19, 47, 238, 31, 76, 90]
[0: [7,77,65,21,50,93,173,115,32,137]
5: [96, 79, 26, 185, 12, 71, 124, 143, 55, 38]
[10] [29, 14, 147, 60, 128, 88, 74, 44, 102, 200]
[15] [106, 240, 63, 48, 91, 19, 160, 31, 76, 135]
[1] [65, 33, 21, 51, 137, 8, 175, 93, 116, 78]
[6] [143, 26, 13, 56, 99, 72, 39, 80, 187, 125]
11: [103, 88, 29, 60, 74, 44, 17, 153, 131, 215]

[31日135、92、76、107、5,164年,63年,20年,50岁,52岁,24岁,35岁,78年,181年,8,138,94,118,65,143,99,81,40岁,13日,127年,72年,188年,27岁,46岁,30岁,60岁,89年,133年,74年,156年,18岁,103年,217年,64年,50岁,135年,92年,21岁,32岁,108年,77年,166年,6,9日,94年,181年,119年,24岁,35岁,139年,68年,53岁,78年,145年,27日,14日,57岁,42岁,100年,190年,82年,73年,127年,89年,18岁,75,61,157,234,133,105,31岁,46岁,113年,21日,7日,92年,64年,32岁,137年,50岁,170年,77年,71年,37岁,26岁,123年,54岁,184年,79年,95年,141年,27岁的74年,86年,14日,102年,146年,127年,43岁的58岁的200年,62年,106年,158年,134年,19岁的[47、238、31、76、90、7、77、65、21、50、93、173、115、32、137、96、79、26、185、12、71、124、143、55、38、29、14、147、60、128、88、74、44、102、200、106、240、63、48、91、19、160、31、76、135、65、33、21、51、137、8、175、93、116、39、80、187、125、103、88、29、60、74、17、153、131、215]

这可以通过一个简单的两步过程来完成。首先使用Fisher-Yates(高德纳)洗牌。然后遍历该列表一次，将其元素复制到新列表中。当遇到元素时，将其插入到新列表中的第一个合法位置。(使用链表比使用数组作为目标要高效得多。)如果没有可以插入的法律位置，则问题的实例是无法解决的。如果你能完成你的目标清单，问题就解决了。最好的情况是O(n)最坏的情况是O(n^2)

• 从列表中删除排列
• 创建5
的周期图
• 根据新图形中有效位置的计数对列表(剩余列表)排序(如果你不这样做，你可能会得到一个错误的不可解，因为放置可以放置更多位置的项目会增加具有更少位置的项目的可能位置计数)
• 继续拾取列表中的物品，将物品添加到循环图中有效位置
• 如果图形中没有有效位置或无法创建图形，则继续下一个
• 如果已创建图形，则返回到已创建图形的开始迭代
• 继续创建其他图形
• 将所有完整图形保存在列表中
• 从列表中随机选择一个
• 如果列表为空则无法解决