与[I]随机置换= I

一般用于具有n个元素的数组的随机排列是指从n!可能性的均匀分布，并且Knuth的洗牌是用来做这样：与[I]随机置换= I

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i 
    exchange a[j] and a[i]

但随着我不知道如何统一形成这样一个排列组合。

例如，n = 3，如何从下面的可能性中随机地构成一个置换？

{1, 2, 0}, {2, 0, 1}

来源

2012-03-07 peter

而不固定点排列称为derangement

作为derangemets的数目是为O（n！），就像排列的数目，生成的所有排列和过滤那些不紊乱不会伤害你的表现。

快速搜索返回我these slides，其中描述了另一种算法。

来源

2012-03-07 09:25:32

谢谢，我还发现这个算法[这里]的正式文件（http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf）。 – peter 2012-03-08 02:36:10

你没有说明你的数组有多大，或者你对于效率的关心程度。一种可能的解决方案就是做Knuth shuffle，然后测试以确定您的约束条件是否满足，如果不是，则重新进行洗牌。

如果你想提高效率，你可以试试这个。由于i正在减少，所以在步骤exchange a[j] and a[i],a[i]被修复之后。所以，简单地修改算法：

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i; repeat until a[j] != i 
    exchange a[j] and a[i]

来源

2012-03-07 09:27:07 Chowlett

复杂性并不重要，但我需要证明它是均匀分布的。满足约束的简单结果是不够的。 – peter 2012-03-07 09:31:03

在了解你的随机函数是，那么这是。原始的Knuth洗牌均匀分布在所有烫发中 - 特别是它具有生成每个约束排列的相等机会。如果结果与约束不匹配，只要将结果扔掉，再次尝试不会改变结果。 – Chowlett 2012-03-07 09:35:09

看看这个：http://stackoverflow.com/questions/7279895/shuffle-list-ensuring-that-no-item-remains-in-same-position，似乎这个算法已经被测试不是制服。 – peter 2012-03-08 02:29:28

与[I]随机置换= I

回答

相关问题