随机播放列表中的一些条件 [英] Shuffle list with some conditions
本文介绍了随机播放列表中的一些条件的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有哪些元素可以使用容易比较等于列表（）。我有洗牌之列，但洗牌必须满足一个条件：
第i个元素 shuffledList [I] 不得在我+/- 1等于元素和元素在我+/- 2 。该清单应考虑循环;也就是说，列表中的最后一个元素后面是第一，反之亦然。
另外，如果可能的话，我想检查洗牌甚至有可能。
注：
我使用C＃4.0。
编辑：
基于一些回应，我会解释一下：
-
名单不会有超过200的元素，所以没有好的表现的实际需要。如果需要2秒来计算的话它不是最好的东西，但它不是世界的末日任。该洗牌名单将被保存，除非真正的名单变化，洗牌名单将被使用。
-
是的，这是一个控制的随机性，但我相信，在这个方法中运行severals将返回不同的洗牌列表。
-
我会做进一步修改后，我尝试下面的一些反应。
编辑2：
-
：失败与Sehe的实现（两者都有解决方案）
- 在两个样本列表
样品1：
`名单，其中，INT＆GT; List1中=新的名单，其中，INT＆GT; {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};`
可能的解决方法：
名单，其中，INT＆GT; shuffledList1 =新的名单，其中，INT＆GT;
{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：
`名单，其中，INT＆GT; list2中=新的名单，其中，INT＆GT; {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};`
-
验证：我用这个方法，它不是最eficient也不优雅一张code我做了，但它的工作：
公共BOOL TestShuffle＆LT; T＆GT;（IEnumerable的＆LT; T＆GT;输入） { 布尔满意= TRUE; INT preV1 = 0; INT preV2 = 0; INT NEXT1 = 0; INT NEXT2 = 0; INT I = 0; 而（ⅰ＆其中; input.Count（）＆安培;＆安培;纳） { preV1 = I - 1; preV2 = I - 2; NEXT1 = i + 1的; NEXT2 = I + 2; 如果（我== 0） { preV1 = input.Count（） - 1; preV2 = preV1 - 1; } 否则，如果（ⅰ== 1） preV2 = input.Count（） - 1; 如果（ⅰ==（input.Count（） - 1）） { NEXT1 = 0; NEXT2 = 1; } 如果（ⅰ==（input.Count（） - 2）） NEXT2 = 0; 满意= （！input.ElementAt（我）.Equals（input.ElementAt（preV1））） ＆功放;＆安培; （！input.ElementAt（我）.Equals（input.ElementAt（preV2））） ＆功放;＆安培; （！input.ElementAt（ⅰ）.Equals（input.ElementAt（NEXT1））） ＆功放;＆安培; （！input.ElementAt（ⅰ）.Equals（input.ElementAt（NEXT2））） ; 如果（满意==假） Console.WriteLine（TestShuffle失败在+ I）; 我++; } 返回满意; }
编辑3：
另外一个测试输入有时会失败：
名单，其中，INT＆GT;项目list3 =新的名单，其中，INT＆GT;（）{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
- 在Linux 32位
- 在单2.11（C＃4.0）编译器与
-optimize +， - 1,000,000
TESTITERATIONS -
VERBOSE不是的#define-d
什么进行了优化：
- 假设输入和输出数组
- 在输入数组中，工作地点
- 在手动
GROUPBY（使用ValueRun结构） - 有这些
ValueRun结构的阵列，而不是可枚举（列表）;排序/洗牌就地 - 使用
不安全块和指针（没有明显区别... 的） - 使用模索引，而不是
MAGIC的LINQ code - 在生成的迭代追加代替嵌套LINQ输出。 这可能有最影响。事实上，它甚至会更好时，我们可以快捷的
ValueRuns表示有countruns集合被责令该计数，它似乎pretty的容易做到的;然而，所述转置的索引（用于环状约束）是复杂的事情。以某种方式将这种优化无论如何增益将更大较大的投入和许多独特的价值观和一些高重复值。的
下面是code与优化版本。 _Additional速度增益可以通过删除随机数发生器的种子可以了;这些仅仅那里使得能够回归测试的输出
[...老code删除，以及...]
原反应的（部分）的
如果我得到你的权利，你想设计一个洗牌的起价结束了连续输出（以2元一个最小交错）p $ pvents重复。
这是不可解在一般情况下。想象一下，只有相同的元素输入：）
更新：事务困扰状态
就像我提到的注意事项，我想我是不是在正确的轨道上所有的时间。要么我应该调用图论（人？），或者使用一个简单的bruteforcey算法来代替，多长埃里克的建议。
无论如何，所以你可以看到我已经达到，而且什么问题（使随机样本快速查看问题）：
＃定义输出//显示测试用例结果
＃定义校验//以自检已内部和验证结果
＃定义SIMPLERANDOM
//将#define DEBUG //真正的痕迹内部
使用系统;
使用System.Linq的;
使用System.Collections.Generic;
公共静态类Q5899274
{
//试车手code
私人const int的TESTITERATIONS = 100000;
公共静态INT主要（字串[] args）
{
VAR测试用例=新的[] {
新的[] {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}，
新的[] {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}，
新 [] { 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，}，
新的[] {} 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4，
} .AsEnumerable（）;
// //创建一些很随意的测试用例
//测试用例= Enumerable.Range（0，10000）。选择（NR =＆GT; Enumerable.Range（GROUPWIDTH，_seeder.Next（GROUPWIDTH，400））选择（EL =＆GT; _seeder.Next（-40，40） ）.ToArray（））;
的foreach（在测试用例VAR测试用例）
{
// _seeder =新随机（45）;的for（int i = 0; I＆LT; TESTITERATIONS;我++）//为标杆/回归
{
尝试
{
无功输出= TestOptimized（测试用例）;
＃如果OUTPUT
Console.WriteLine（S $ P $垫\ t {0}的string.join（，输出））;
#ENDIF
＃如果校验
AssertValidOutput（输出）;
#ENDIF
}赶上（例外五）
{
Console.Error.WriteLine（异常输入{0}的string.join（，测试用例））;
Console.Error.WriteLine（序列长度{0}：{1}组和其余{2}，testcase.Count（），（testcase.Count（）+ GROUPWIDTH-1）/ GROUPWIDTH，testcase.Count（）％ GROUPWIDTH）;
Console.Error.WriteLine（分析：\ñ\ t {0}的string.join（\ñ\ t的，InternalAnalyzeInputRuns（测试用例）））;
Console.Error.WriteLine（E）;
}
}
}
返回0;
}
＃地区的算法核心
const int的GROUPWIDTH = 3; / *暗示的2的最小距离
重复的（GROUPWIDTH-1）值
必须保证* /
公共静态T [] TestOptimized＆LT; T＆GT;（T []输入，布尔doShuffle = FALSE）
其中T：IComparable的＆LT; T＆GT;
{
如果（input.Length == 0）
返回输入;
变种运行= InternalAnalyzeInputRuns（输入）;
＃如果校验
CanBeSatisfied（input.Length，运行）; //抛出NoValidOrderingExists如果不
#ENDIF
VAR换位= CreateTranspositionIndex（input.Length，运行）;
INT POS = 0;
对于（INT RUN = 0;运行＆LT; runs.Length;运行++）
的for（int i = 0; I＆LT;运行[运行] .runlength;我++）
输入[换位[POS +] =运行[运行] .value的;
返回输入;
}
私有静态ValueRun＆LT; T＆GT; [] InternalAnalyzeInputRuns＆LT; T＆GT;（T []输入）
{
VAR listOfRuns =新的名单，其中，ValueRun＆LT; T＆GT;＆GT;（）;
的Array.Sort（输入）;
ValueRun＆LT; T＆GT;目前=新ValueRun＆LT; T＆GT; {值=输入[0]，游程= 1};
的for（int i = 1; I＆LT; = input.Length;我++）
{
如果（I＆LT; input.Length和放大器;＆放大器;输入[I] .Equals（current.value））
current.runlength ++;
其他
{
listOfRuns.Add（电流）;
如果（ⅰ＆其中; input.Length）
目前=新ValueRun＆LT; T＆GT; {值=输入[I]中，游程= 1};
}
}
＃如果SIMPLERANDOM
变种RNG =随机新（_seeder.Next（））;
listOfRuns.ForEach（RUN =＆GT; run.tag = rng.Next（））; //这个洗牌它们
#ENDIF
变种运行= listOfRuns.ToArray（）;
的Array.Sort（运行）;
返回运行;
}
//注：最佳性能
// *一些步骤可以内嵌CreateTranspositionIndex来完成的
// 效率
私有类NoValidOrderingExists：异常{公共NoValidOrderingExists（字符串消息）：基地（消息）{}}
私有静态布尔CanBeSatisfied＆LT; T＆GT;（INT长度，ValueRun＆LT; T＆GT; []运行）
{
INT组=（长+ GROUPWIDTH-1）/ GROUPWIDTH;
INT余数=长度％GROUPWIDTH;
//基本检查
如果（长度LT; GROUPWIDTH）
抛出新NoValidOrderingExists（的String.Format（输入序列较短（{0}）比单组{1}），长度，GROUPWIDTH））;
如果（runs.Length＆LT; GROUPWIDTH）
抛出新NoValidOrderingExists（的String.Format（不足不同的值（{0}）中输入序列填单组{1}），runs.Length，GROUPWIDTH））;
INT effectivewidth = Math.Min（GROUPWIDTH，长度）;
//检查是否有直接用尽通过重复单个值以上基团的可用数量（用于相关groupmember如果有剩余基团）
对于（INT groupmember = 0; groupmember＆LT; effectivewidth; groupmember ++）
{
INT容量=余== 0？组：组-1;
如果（容量＆LT;运行[groupmember] .runlength）
抛出新NoValidOrderingExists（的String.Format（能力突破上groupmember指数{0} {1}元素的能力，（游程{2}在运行{3}）），
groupmember，容量，运行[groupmember] .runlength，运行[groupmember] .value的））;
}
//与上述，没有单一ValueRun应该是一个问题;然而，由于
//空间耗尽的重复可能最终会被挤压到
//'余数'基团，其可以是一个不完整的组;
//特别是，如果最小ValueRun（尾）具有游程大于1
// _and_有一个不完全余基，有一个问题
如果（runs.Last（）游程长度GT。1安培;＆安培;！（0 =余数））
抛出新NoValidOrderingExists（最小ValueRun会蔓延到尾部残缺集团）;
返回true;
}
//也将验证输入序列的可解
私有静态诠释[] CreateTranspositionIndex＆LT; T＆GT;（INT长度，ValueRun＆LT; T＆GT; []运行）
其中T：IComparable的＆LT; T＆GT;
{
INT余数=长度％GROUPWIDTH;
INT effectivewidth = Math.Min（GROUPWIDTH，长度）;
VAR换位=新INT [长度];
{
INT outit = 0;
对于（INT groupmember = 0; groupmember＆LT; effectivewidth; groupmember ++）
对于（INT POS = groupmember; outit＆LT;长度放大器;＆安培; POS≤（长余数）/ *避免剩余* /; POS + = GROUPWIDTH）
换位[outit ++] = POS机;
而（outit＆LT;长度）
{
换位[outit] = outit;
outit + = 1;
}
＃如果调试
INT组=（长+ GROUPWIDTH-1）/ GROUPWIDTH;
Console.WriteLine（自然换位（{1} {0}中的单元组，其余{2}）：，组，长度，余数）;
Console.WriteLine（\ t {0}的string.join（，换位））;
变种SUM1 =的string.join（：，Enumerable.Range（0，长度））;
变种SUM2 =的string.join（：，transpositions.OrderBy（ⅰ= I标记））;
如果（SUM1！= SUM2）
抛出新的ArgumentException（换位不包括范围\ñ\ tsum1 =+ SUM1 +\ñ\ tsum2 =+ SUM2）;
#ENDIF
}
返回换位;
}
#endregion //算法核心
＃地区公用事业
私人结构ValueRun＆LT; T＆GT; ：IComparable的＆LT; ValueRun＆LT; T＆GT;＆GT;
{
公众的T值;
公众诠释游程;
公众诠释标签; //设置为随机洗牌
公众诠释的CompareTo（ValueRun＆LT; T＆gt;其他）{VAR RES = other.runlength.CompareTo（游程）;返回0 ==资源？ tag.CompareTo（other.tag）：资源; }
公共重写字符串的ToString（）{返回的String.Format（[{0}×{1}]，游程，值）; }
}
私有静态/ *只读* /随机_seeder =新的随机（45）;
#endregion //公用事业
＃地区错误检测/认证
公共静态无效AssertValidOutput＆LT; T＆GT;（IEnumerable的＆LT; T＆GT;输出）
其中T：IComparable的＆LT; T＆GT;
{
VAR REPL = output.Concat（output.Take（GROUPWIDTH））的ToArray（）。
的for（int i = 1; I＆LT; repl.Length;我++）
为（诠释J = Math.Max（0，异（GROUPWIDTH-1））; J＆所述; I; J ++）
如果（REPL [I] .Equals（REPL [J]））
抛出新的ArgumentException（的String.Format（不正确的重复距离发现：（＃{0};＃{1}）超出{2}：值是{3}'，J，I，output.Count（） REPL [J]））;
}
#endregion
}
I have a list of elements which can be easily compared using Equals(). I have to shuffle the list, but the shuffle must satisfy one condition:
The i'th element shuffledList[i] must not equal elements at i +/- 1 nor elements at i +/- 2. The list should be considered circular; that is, the last element in the list is followed by the first, and vice versa.
Also, if possible, I would like to check if the shuffle is even possible.
Note:
I'm using c# 4.0.
EDIT:
Based on some responses, I will explain a little more:
The list wont have more than 200 elements, so there isn't a real need for good performance. If it takes 2 secs to calculate it it's not the best thing, but it's not the end of the world either. The shuffled list will be saved, and unless the real list changes, the shuffled list will be used.
Yes, it's a "controlled" randomness, but I expect that severals run on this method would return different shuffled lists.
I will make further edits after I try some of the responses below.
EDIT 2:
- Two sample list that fails with Sehe's implementation (Both have solutions):
Sample1:
`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};`
Possible solution:
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}
Sample 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};`
Verify: I'm using this method, that it's not the most eficient nor elegant piece of code I've made, but it does it's work:
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; }
EDIT 3:
Another test input that fails sometimes:
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};
解决方案
Optimized version
To my disappointment, my optimized function only runs 7x faster than the LINQ 'straightforward' version. Unoptimized LINQ 1m43s Optimized 14.7s.
- linux 32-bit
- Mono 2.11 (C# 4.0) compiler with
-optimize+, - 1,000,000
TESTITERATIONS VERBOSEnot#define-d
What has been optimized:
- assume arrays for input and output
- work in-place on input array
- 'manually' analyze runs of identical values, instead of using
GroupBy(usingValueRunstruct) - have these
ValueRunstructs in an Array instead of Enumerable (List); sort/shuffle in-place - use
unsafeblocks and pointers (no discernable difference...) - use modulo indexing instead of
MAGICLinq code - generate the output by iterative append instead of nested LINQ. This probably had the most effect. Actually, it would be even better when we could shortcut the
ValueRuns that have a countruns collection is being ordered by this count, it seemed pretty easy to do; however, the transposed indexing (needed for the cyclic constraints) is complicating things. The gain of somehow applying this optimization anyway will be bigger with larger inputs and many unique values and some highly duplicated values.
Here is the code with optimized version. _Additional speed gain can be had by removing the seeding of RNGs; these are only there to make it possible to regression test the output.
[... old code removed as well ...]
Original response (partial)
If I'm getting you right, you are trying to devise a shuffle that prevents duplicates from ending up consecutive in the output (with a minimum interleave of 2 elements).
This is not solvable in the general case. Imagine an input of only identical elements :)
Update: Troubled state of affairs
Like I mention in the notes, I think I wasn't on the right track all the time. Either I should invoke graph theory (anyone?) or use a simple 'bruteforcey' algorithm instead, much a long Erick's suggestion.
Anyway, so you can see what I've been up to, and also what the problems are (enable the randomized samples to quickly see the problems):
#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
}
这篇关于随机播放列表中的一些条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
