c# - 有条件的随机播放列表

Question

我有一个元素列表，可以使用 Equals() 轻松比较这些元素.我必须打乱列表，但打乱必须满足一个条件:

第 i 个元素 shuffledList[i]不得等于 i +/- 1 处的元素也不是 i +/- 2 处的元素.该列表应被认为是循环的；也就是说，列表中的最后一个元素后跟第一个元素，反之亦然。

此外，如果可能的话，我想检查一下洗牌是否可行。

备注:

我正在使用 C# 4.0。

编辑:

根据一些回复，我再解释一下:

• 该列表的元素不会超过 200 个，因此没有真正需要良好的性能。如果需要 2 秒来计算它，那不是最好的事情，但也不是世界末日。打乱后的名单会被保存，除非真正的名单发生变化，否则会使用打乱后的名单。

• 是的，这是一个“受控”的随机性，但我预计在这个方法上运行的多个程序会返回不同的随机列表。

• 我会在尝试下面的一些回复后进行进一步的编辑。

编辑 2:

• Sehe 实现失败的两个示例列表(都有解决方案):

示例 1:

`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> shuffledList1 = new List<int>
{9,3,1,4,7,9,2,6,8,1,4,9,2,0,6,5,7,8,4,3,10,9,6,7,8,5,3,9,1,2,7,8}

示例 2:

`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};`

• 验证:我正在使用这种方法，它不是我编写的最高效也不是最优雅的代码片段，但它确实有效:

  public bool TestShuffle<T>(IEnumerable<T> input)
  {
      bool satisfied = true;
      int prev1 = 0; int prev2 = 0;
      int next1 = 0; int next2 = 0;
      int i = 0;
      while (i < input.Count() && satisfied)
      {
          prev1 = i - 1; prev2 = i - 2; next1 = i + 1; next2 = i + 2;
          if (i == 0)
          {
              prev1 = input.Count() - 1;
              prev2 = prev1 - 1;
          }
          else if (i == 1)
              prev2 = input.Count() - 1;
          if (i == (input.Count() - 1))
          {
              next1 = 0;
              next2 = 1;
          }
          if (i == (input.Count() - 2))
              next2 = 0;
          satisfied =
                  (!input.ElementAt(i).Equals(input.ElementAt(prev1)))
              && (!input.ElementAt(i).Equals(input.ElementAt(prev2)))
              && (!input.ElementAt(i).Equals(input.ElementAt(next1)))
              && (!input.ElementAt(i).Equals(input.ElementAt(next2)))
          ;
          if (satisfied == false)
              Console.WriteLine("TestShuffle fails at " + i);
          i++;
      }
      return satisfied;
  }
  

编辑 3:

另一个有时会失败的测试输入:

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};

Answer 1

优化版

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

• Linux 32 位
• 带有 -optimize+ 的 Mono 2.11 (C# 4.0) 编译器，
• 1,000,000 测试
• VERBOSE 不是 #define-d

优化了什么:

• 假设输入和输出数组
• 就地处理输入数组
• “手动”分析相同值的运行，而不是使用 GroupBy(使用 ValueRun 结构)
• 将这些 ValueRun 结构放在数组中而不是 Enumerable (List) 中；就地排序/随机播放
• 使用不安全 block 和指针(没有明显的区别...)
• 使用模索引代替 MAGIC Linq 代码
• 通过迭代追加而不是嵌套 LINQ 生成输出。 这可能是最有效的。实际上，如果我们可以将具有 countruns 集合的 ValueRun 设置为按此计数排序的快捷方式，那就更好了，这似乎很容易做到；然而，转置索引(循环约束所需)使事情复杂化。无论如何，以某种方式应用此优化的 yield 将随着更大的输入和许多唯一值以及一些高度重复的值而变得更大。

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

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

---

原始回复(部分)

如果我没看错，您正在尝试设计一种洗牌，以防止重复项在输出中连续结束(最少交错 2 个元素)。

这在一般情况下是无法解决的。想象一下只有相同元素的输入:)

更新:麻烦事态

就像我在笔记中提到的，我认为我一直没有走在正确的轨道上。要么我应该引用图论(有人吗？)，要么改用简单的“bruteforcey”算法，这是 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

}