生成元素随机顺序的算法

如何随机化大约20个具有最低复杂度的元素的顺序？（产生随机排列）生成元素随机顺序的算法

来源

2009-11-07 Ante

cca是什么意思？ – 2009-11-07 01:48:33

典型相关分析？ – 2009-11-07 01:49:04

你是什么意思？：P – 2009-11-07 01:51:07

Knuth's shuffle algorithm是一个不错的选择。

来源

2009-11-07 02:33:48

坦率地说，任何人都说过别的话令人失望。 – 2009-11-07 03:31:08

我很失望，那是答案。既然你必须首先遍历列表来填充它，然后洗牌（用一个公认的好算法），我会认为有更好的解决方案。 – SourceOverflow 2017-10-30 11:37:29

几个月前我博客了一个整数列表的随机排列。你可以使用它作为包含你的元素的集合的索引的排列，然后你有你想要的。

在第一篇文章我探讨一些可能性，最终我获得 “功能来随机排列替换用O（n）的复杂性泛型列表” ，适当封装以处理不可变数据（即，它是无副作用的）。

在第二篇文章中，我使它均匀分布。

代码是在F＃中，我希望你不介意！

祝你好运。

编辑：我没有正式的证明，但直觉告诉我，这样的算法的复杂度不能低于为O（n）。我真的很感激看到它更快完成！

来源

2009-11-07 01:51:47

递归在第二篇文章很简单..我想我可以使用它.. – Ante 2009-11-07 02:09:21

所有的排列必须是可能的，并且将一个数组重新排列成一个排列（即，排列“p”，对于所有的'k'，对于该排列'p（k）！= k'）要求每个元素被访问。因此O（n）最坏的情况。还是还不够正式？ – 2009-11-07 03:25:32

同样为O（n）由相同的证明平均的情况下，来想起来，因为IIRC当n接近于无穷大的（1 ... N），它们是紊乱的排列的比例接近1/e的。 – 2009-11-07 03:27:00

一个简单的随机顺序方法是创建一个正确大小的新列表（在你的情况下为20），遍历第一个列表，并将每个元素随机添加到第二个列表中。如果随机位置已经填满，则将其置于下一个空闲位置。

我觉得这个伪代码是正确的：

list newList 
foreach (element in firstList) 
    int position = Random.Int(0, firstList.Length - 1) 
    while (newList[position] != null) 
     position = (position + 1) % firstList.Length 
    newList[position] = element

编辑：所以事实证明，这个答案是不实际的好。它既不是特别快，也不是特别随机。谢谢您的意见。对于一个很好的答案，请回滚到页面顶部:-)

来源

2009-11-07 02:15:23

在最坏的情况下，这个算法是O（n^2）（即如果你的随机数发生器说“1,1,1,1,1,1,1 ...”，我让你计算其余的），不是非常优化。 – 2009-11-07 02:23:29

将物品放在下一个空闲位置使其不那么随意。这些项目将保持其原始顺序，而不是真正的随机洗牌。为了解决这个问题，你必须在一个位置被选中时选择一个新的随机位置，这当然会让它变慢很多。 – Guffa 2009-11-07 03:00:56

这是一个好点的Guffa。我从来没有意识到这一点。谢谢。至少我在这里学到了一些东西:-) – 2009-11-07 03:19:20

可能有人已经为您实施了洗牌。例如，在Python中，您可以使用random.shuffle，C++ random_shuffle和PHP shuffle。

来源

2009-11-07 02:32:47

hmm .. php也许？ – Ante 2009-11-07 03:07:24

令人惊讶的是，在PHP中它被称为'shuffle' :)我会更新我的答案。 – 2009-11-07 14:08:43

生成元素随机顺序的算法

回答

相关问题