如何以最低的复杂度随机排列大约20个元素？（生成随机排列）
4个回答
22
Knuth 洗牌算法 是一个不错的选择。
- David R Tribble
1
1我很失望这就是答案。因为你必须首先迭代整个列表来填充它，然后再用一个确实不错的算法来洗牌，所以我认为应该有更好的解决方案。 - SourceOverflow
2
几个月前，我在博客中介绍了如何获取整数列表的随机排列。您可以使用该排列作为包含元素索引的置换，然后您就可以得到想要的结果。
在第一篇文章中，我探讨了一些可能性，最终得到了“用O(n)的复杂度对通用列表进行随机排列”的函数，并适当封装以在不可变数据上工作（即，它是无副作用的）。
在第二篇文章中，我使其均匀分布。
代码使用F#编写，希望您不介意！
祝你好运。
编辑：我没有正式的证明，但直觉告诉我，这种算法的复杂度不能低于O(n)。如果有更快的算法，请分享给我，我将不胜感激！
- Bruno Reis
2
1所有排列都必须是可能的，将数组重新排列成一个错排（即，对于所有
k，都有p(k) != k的排列p）需要访问每个元素。因此最坏情况下时间复杂度为O(n)。或者这样说还不够正式吗？ - Steve Jessop同样根据证明，平均情况下的时间复杂度也是O(n)，顺便提一下，如果我没记错的话，当n趋近于无穷大时，(1...n)的排列中为错排的比例趋近于1/e。 - Steve Jessop
1
一个简单的随机排序方法是创建一个新的正确大小的列表（在您的情况下为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
编辑：事实证明，这个答案并不是很好。它既不特别快，也不特别随机。感谢您的评论。要获得一个好的答案，请滚动回页面顶部 :-)
- David Johnstone
3
在最坏的情况下，这个算法是O(n^2)（即，如果你的随机数生成器出现了“1, 1, 1, 1, 1, 1, 1, ...”这种序列，我就让你自己计算剩下的部分），并不是非常优化。 - Bruno Reis
2将项目放在下一个空闲位置会使其不那么随机。与真正的随机洗牌相比，项目将保持其原始顺序更多。要解决这个问题，您需要在占据位置时选择一个新的随机位置，这当然会使它变得更慢。 - Guffa
那是一个很好的观点，Guffa。我之前从未意识到过。谢谢你。至少我在这里学到了一些东西 :-) - David Johnstone
1
有可能已经有人为您实现了洗牌功能。例如，在 Python 中，您可以使用random.shuffle，在 C++ 中使用 random_shuffle，在 PHP 中使用 shuffle。
- Roberto Bonvallet
1
令人惊讶的是，在PHP中它被称为“shuffle” :) 我会更新我的答案。 - Roberto Bonvallet
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接