如何对数组进行混洗以使所有元素都改变它们的位置

Question

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

Answer 1

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 2

那这个呢？

1. 分配一个包含从0到arrayLength-1的数字的数组
2. 随机播放阵列
3. 如果数组中没有索引等于其值的元素,则继续执行步骤4; 否则从第2步重复.
4. 使用混洗数组值作为数组的索引.