有些条件的随机播放列表

我有一个元素列表，可以使用Equals()轻松比较。 我必须洗牌，但洗牌必须满足一个条件：

第i个元素shuffledList[i]必须不等于i +/- 1元素和i +/- 2处的元素。 该清单应视为循环; 也就是说，列表中的最后一个元素后跟第一个元素，反之亦然。

另外，如果可能的话，我想检查一下是否可以进行随机播放。

注意：

我正在使用c＃4.0。

编辑：

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

• 该列表不会有超过200个元素，因此不需要良好的性能。 如果计算它需要2秒钟，这不是最好的事情，但它也不是世界末日。 将保存随机列表，除非真实列表发生更改，否则将使用随机列表。

• 是的，它是一个“受控”的随机性，但我希望在这个方法上运行的几个会返回不同的洗牌列表。

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

编辑2：

• 两个样本列表因Sehe的实现而失败（两者都有解决方案）：

样本1：

 `List list1 = new List{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 shuffledList1 = new List {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 list2 = new List {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};` 

• validation：我正在使用这种方法，它不是我制作的最有效和最优雅的代码片段，但它确实有效：

   public bool TestShuffle(IEnumerable 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 list3 = new List(){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

优化版

令我失望的是，我的优化function仅比LINQ’简单’版本快了7倍。 未经优化的LINQ 1m43s优化了14.7秒 。

• linux 32位
• 使用-optimize+ Mono 2.11（C＃4.0）编译器，
• 1,000,000次TESTITERATIONS
• VERBOSE不是#define -d

已优化的内容：

• 假设输入和输出的数组
• 在输入数组上就地工作
• ‘手动’分析相同值的运行，而不是使用GroupBy （使用ValueRun结构）
• 将这些ValueRun结构放在Array而不是Enumerable（List）中; 在原地排序/随机播放
• 使用unsafe块和指针（ 没有可辨别的差异…… ）
• 使用模数索引而不是MAGIC Linq代码
• 通过迭代追加而不是嵌套LINQ生成输出。 这可能效果最好。 实际上，当我们可以快速ValueRun时会更好，因为这个计数器正在按顺序排列，这似乎很容易做到; 然而，转置索引（循环约束所需）使事情变得复杂。 无论如何应用此优化的收益将随着更大的输入和许多唯一值以及一些高度重复的值而变得更大。

这是具有优化版本的代码。 _通过移除RNG的种子可以获得额外的速度增益; 这些仅用于回归测试输出。

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

---

原始回复（部分）

如果我找对了你，你试图设计一个shuffle来防止重复在输出中连续结束（最少交错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(T[] input, bool doShuffle = false) where T: IComparable { 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[] InternalAnalyzeInputRuns(T[] input) { var listOfRuns = new List>(); Array.Sort(input); ValueRun current = new ValueRun { value = input[0], runlength = 1 }; for (int i=1; i<=input.Length; i++) { if (i { 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(int length, ValueRun[] runs) { int groups = (length+GROUPWIDTH-1)/GROUPWIDTH; int remainder = length % GROUPWIDTH; // elementary checks if (length1 // _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(int length, ValueRun[] runs) where T: IComparable { int remainder = length % GROUPWIDTH; int effectivewidth = Math.Min(GROUPWIDTH, length); var transpositions = new int[length]; { int outit = 0; for (int groupmember=0; groupmemberi)); 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 : IComparable> { public T value; public int runlength; public int tag; // set to random for shuffling public int CompareTo(ValueRun 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(IEnumerable output) where T:IComparable { var repl = output.Concat(output.Take(GROUPWIDTH)).ToArray(); for (int i=1; i 

Answer 2

您的要求消除了真正的改组替代方案：没有随机性，或者存在受控随机性。 这是一种特殊的方法

1. 对原始列表L排序
2. 找到模式M及其频率n
3. 如果n是偶数，那么n ++。
4. 创建k （= 5 * n – 1）个列表（素数为n ， n 5倍） L ₁到L _k
   （选择5以避免前两个元素和两个下一个元素）
5. 以循环方式将所有元素分配到k列表中
6. 单独洗牌所有k列表。
7. 按以下顺序整理k列表的内容：a。 随机选择+5或-5作为x 。
   湾 选择一个随机数j 。
   C。 重复k次：
   一世。 添加L _j中的所有内容。
   II。 j < - （ 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,135,137,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]

模式频率= 4，因此19个插槽（＃0 – ＃18）

0：[7,21,32,50,65,77,93,115,137,173]
1：[8,21,33,51,65,78,93,116,137,175]
2：[8,24,35,52,65,78,94,118,138,181]
3：[9,24,35,53,68,78,94,119,139,181]
4：[10,26,37,54,71,79,95,123,141,184]
5：[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]
8：[14,27,42,57,73,82,100,127,145,190]
9：[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]
14：[19,31,47,62,76,90,106,134,158,238]
15：[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]
18：[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]
9：[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,57,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,10,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,78,143,26,13,56,99 ，72,39,80,187,125,103,88,29,60,74,44,17,153,131,215]

Answer 3

它可以通过简单的两步过程完成。 首先使用Fisher-Yates（Knuth）shuffle。 然后迭代列表一次，将其元素复制到新列表。 遇到元素时，将其插入新列表中的第一个合法位置。 （对于链接列表而言，这将比使用数组作为目标更有效。）如果没有要插入的合法位置，则问题的实例无法解决。 如果您设法填写目的地列表，问题就解决了。 这将在最佳情况下采用O（n）并且在最差情况下采用O（n ^ 2）。

Answer 4

• 在列表中置换有效5，如果没有无法解决的话
• 从列表中删除排列
• 创建一个5的循环图
• 通过新图表中有效位置的计数来排序列表（剩余列表）（如果你不这样做，你最终会得到一个错误的不可解决的问题，因为放置更多位置的项目可以增加项目的可能位置数量）
• 继续选择列表中的项目，将项目添加到有效位置的循环图表
• 如果图形或图形中没有有效位置，则无法继续创建下一个
• 如果创建的图形还原为开始迭代，其中已创建图形
• 继续创建其他图表
• 将所有完整图表保存在列表中
• 从该列表中随机选择一个
• 如果列表是空的无法解决的