优化版本

令我失望的是，我的优化功能仅比LINQ“简单”版本运行速度快7倍。 未 优化LINQ 1m43s 优化 14.7s 。

• Linux 32位
• 具有的Mono 2.11（C＃4.0）编译器-optimize+，
• 1,000,000 TESTITERATIONS
• VERBOSE不是#define-d

已优化的内容：

• 假定用于输入和输出的数组
• 在输入数组上就地工作
• “手动”分析具有相同值的运行，而不是使用GroupBy（使用ValueRun结构）
• 将这些ValueRun结构放在数组中，而不是在Enumerable（List）中；就地排序/随机播放
• 使用unsafe块和指针（ 没有明显的区别… ）
• 使用模索引而不是MAGICLinq代码
• 通过迭代追加而不是嵌套的LINQ生成输出。 这可能影响最大。 实际上，当我们可以快捷地将ValueRun具有countruns集合的s按此计数排序时，这会更好，这似乎很容易做到；但是，转置索引（需要循环约束）使事情变得复杂。无论如何，使用较大的输入，许多唯一值和一些高度重复的值，无论如何应用此优化都会带来更大的收益。

这是具有优化版本的代码。_通过消除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

    }