洗牌的最佳算法是什么？

Question

鉴于一组有限的N卡,什么是最好的方法(算法)洗牌,所以我将有最好的洗牌包卡,最小的步骤,以获得最大的随机排列？

最小步骤的最佳解决方案是什么？

Answer 1

使用Fisher Yates算法.许多编程语言使用该算法的变体来混淆有限集的元素.这是Fisher Yates算法的伪代码(Richard Durstenfeld的优化版本):

-- To shuffle an array a of n elements (indices 0..N-1):
for i from N?1 downto 1 do
     j ? random integer such that 0 ? j ? i
     exchange a[j] and a[i]

该算法确保均匀分布.对于N卡,有N!混乱的组合可能.在这里,任何N!排列同样可能被返回.时间复杂性是O(N).