algorithm - 洗牌数组的最佳算法

Question

我有一个数组 s = {'ACA','BBC','CKA',...};

我想洗牌s。所以我创建列表 A={1,2,3,4..} 和列表 B={1,2,3,4,...}

然后，我将两个列表打乱。 随机洗牌(A) 随机.shuffle(B)

最后，我将 s[A[0]] 与 s[B[0]] 交换，将 s[A[1]] 与 s[B[1]] 交换......

此算法是否会生成 s 的随机排列？够随意吗？假设 random.shuffle 产生足够随机的 A 和 B 排列。

Answer 1

要使用带有索引数组的 Fisher--Yates (Knuth) 洗牌，初始化单个索引数组 A 就像

for (int i = 0; i < n; i++) A[i] = /* random integer in 0..i */;

然后像这样交换

for (int i = 0; i < n; i++) swap(&s[A[i]], &s[i]);

您的算法不会生成统一的随机排列。当n=2时，A和B的可能性为

A = {0, 1}; B = {0, 1};
A = {0, 1}; B = {1, 0};
A = {1, 0}; B = {0, 1};
A = {1, 0}; B = {1, 0};

这些都不会对起始排列产生任何影响；要么两个元素相互交换，要么相同的重要交换重复两次，取消其效果。