c++ - 如何打乱数组以使所有元素更改其位置

Question

我需要打乱一个数组，以便所有数组元素都应该改变它们的位置。给定一个数组[0,1,2,3]，可以获取[1,0,3,2]或[3,2,0,1]不获取[3,1,2,0]（因为2保持不变）。std::random_shuffle我想算法不是特定于语言的，但以防万一，我在 C++ 程序中需要它（由于额外的要求，我不能使用）。

Answer 1

那这个呢？

1. 分配一个包含从 0 到 arrayLength-1 的数字的数组
2. 随机排列数组
3. 如果数组中没有索引等于其值的元素，则继续执行步骤4；否则从第 2 步开始重复。
4. 使用洗牌后的数组值作为数组的索引。

Answer 2

For each element e
    If there is an element to the left of e
        Select a random element r to the left of e
           swap r and e

这保证了每个值都不在它开始的位置，但不保证如果有重复，每个值都会改变。

BeeOnRope指出，虽然简单，但这是有缺陷的。给定列表 [0,1,2,3]，此算法无法生成输出 [1,0,3,2]。

Answer 3

它不会很随机，但您可以将所有元素旋转至少一个位置：

std::rotate(v.begin(), v.begin() + (rand() % v.size() - 1) + 1, v.end());

如果v在{1,2,3,4,5,6,7,8,9}开始时是，那么在旋转之后它将是，例如：{2,3,4,5,6,7,8,9,1}， 或{3,4,5,6,7,8,9,1,2}，等等。

数组的所有元素都会改变位置。

Answer 4

我有一个想法，希望它适合您的应用程序。再拥有一个容器，这个容器将是一个 "map(int,vector(int))" 。关键元素将显示索引，向量的第二个元素将保存已使用的值。

例如，对于第一个元素，您将使用 rand 函数来查找应该使用数组的哪个元素。然后，如果数组的该元素已用于该索引，您将检查映射结构。