我在Coding Horror上读过一篇关于各种shuffle算法的文章.我已经看到人们已经在某个地方对列表进行了洗牌:
var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
这是一个很好的shuffle算法吗？它是如何工作的？这样做是否可以接受？
在给定任意种子值的情况下,是否有任何已知的算法可以在线性时间和常数空间(当迭代生成输出时)生成混洗范围[0..n]？
假设n可能很大,例如数百万,因此不需要潜在地产生每种可能的排列,尤其是因为它是不可行的(种子值空间需要很大).这也是需要恒定空间的原因.(所以,我特别不是在寻找一种阵列混洗算法,因为这需要将范围存储在长度为n的数组中,因此会使用线性空间.)
我知道问题162606,但它没有给出这个特定问题的答案 - 从排列索引到该问题中给出的排列的映射需要巨大的种子值空间.
理想情况下,它的行为类似于具有周期和范围的LCGn,但选择a和c制作LCG 的艺术是微妙的.只要满足约束a,并c在一个完整周期LCG可满足我的要求,但如果有更好的想法在那里我想知道.
我有一份n项清单.我想要一个算法让我随机从该集合中选择一个可能无限的项目序列,但有几个约束条件:
基本上,我想要一个算法为MP3播放器生成播放列表,打开'shuffle'和'repeat',这样可以确保它不会播放太靠近自己的同一首歌,并确保它能均匀播放所有歌曲,没有明显的模式.
这些限制消除了争用的两个明显的解决方案:
一个天真的解决方案可能是随机挑选,但拒绝选秀权,如果他们发生在上米选秀权; 这意味着保留m个先前选择的列表,并且每次都对该列表检查每个选择,这使得算法不确定并且同时变慢 - 失败.除非我遗漏了一些明显的东西......
所以我有一个我正在使用的算法,我有点不满意.我用一副牌来比喻它,我有一个画堆和弃牌堆.我从完整的清单开始,洗牌,在抽签堆中,丢弃堆空.从绘图堆的顶部读取下一个项目,然后放入丢弃堆中.一旦丢弃堆达到一定的尺寸(m项),我就将它移动,并将其移动到拉桩的底部.
这符合要求,但是这一次洗牌每米挑选困扰我.通常是O(1),但是m(m)一次是O(m).平均而言,这相当于一个恒定的时间,但必须有一个更清洁的解决方案,随着时间的推移丢弃丢弃物.
在我看来,这是一个如此简单,通用和常见的问题,它必须具有其中一种双管算法,如Fisher-Yates或Boyer-Moore.但是我的谷歌显然并不强大,因为我还没有找到定位不可避免的1973年ACM论文的术语集,这些论文可能解释了在O(1)时间内如何做到这一点,以及为什么我的算法存在严重缺陷某种程度上来说.
我试图用随机序列中1-20的数字填充20个整数的数组.这是我的代码:
int lookup[20]={0};
int array[20]={0};
srand(time(NULL));
for(int i=0;i<20;++i){
bool done=false;
while(!done){
int n=rand()%20;
if(lookup[n]==0){
array[i]=n;
lookup[n]=1;
done=true;
}
}
}
我创建了一个查找数组来检查是否还没有选择随机数并将其存储在数组中.正如你所看到的,我创建了2个循环,一个用于遍历数组,而while用于选择随机数.在每次循环迭代中,数字可能会重新出现并导致另一个while循环.有没有更快的方法来做到这一点？
如何实现一个随机数生成器,给定一个间隔,(随机)生成该间隔中的所有数字,而不重复？
它应该消耗尽可能少的时间和内存.
刚刚发明的C#-ruby-ish伪代码中的示例:
interval = new Interval(0,9)
rg = new RandomGenerator(interval);
count = interval.Count // equals 10
count.times.do{
print rg.GetNext() + " "
}
这应该输出如下:
1 4 3 2 7 5 0 9 8 6
我有二维数组.我想随机选择一个插槽,并继续这样做,从不选择相同的插槽两次,直到我最终选择所有插槽(所以当然最后一个选择没有任何随机).这是一个众所周知的算法吗？我正在使用C#,但显然这更多是关于算法而不是任何特定平台.是的,'大书'在我的购买清单上:)