language-agnostic - 随机排序数组

Question

是否存在一种算法，给定一个有序的符号列表 {a1, a2, a3, ..., ak}，在 O(n) 时间内以随机顺序无偏差地生成相同符号的新列表？ “无偏差”意味着任何符号 s 最终出现在列表中某个位置 p 的概率为 1/k。

假设可以在 O(1) 时间内从 1-k 生成一个无偏整数。还假设 O(1) 元素访问/变异是可能的，并且可以在 O(k) 时间内创建一个大小为 k 的新列表。

特别是，我会对“生成”算法感兴趣。也就是说，我会对具有 O(1) 初始开销的算法感兴趣，然后为列表中的每个插槽生成一个新元素，每个插槽花费 O(1) 时间。

如果所描述的问题不存在解决方案，我仍然想知道通过以下一种或多种方式(和/或其他方式，如有必要)不满足我的约束的解决方案:

时间复杂度比 O(n) 差。

算法在符号的最终位置方面存在偏差。

算法不是生成性的。

我应该补充一点，这个问题似乎与从 1-k 中随机排序整数的问题相同，因为我们可以从 1-k 中对整数列表进行排序，然后对于新列表中的每个整数 i，我们可以产生符号 ai。

Answer 1

是的 - Knuth Shuffle 。