ruby - 这个shuffle算法对吗？

Question

下面是我用ruby实现的shuffle算法:

def shuffle03!(arr)
    len = arr.length
    for i in 0..len-1
        index1 = Random.rand(0..len-1)
        index2 = Random.rand(0..len-1)
        arr[index1], arr[index2] = arr[index2], arr[index1]
    end
end

我通过推算测试了这个算法:

class ShuffleTest
    def initialize(seed)
        len = seed.length
        @count = {}
        for i in 0..len-1
            @count[seed[i]] = Array.new(len, 0)
        end
    end
    def test(arr)
        for i in 0...arr.length
            @count[arr[i]][i] += 1
        end
    end
    def show_count
        return @count
    end
end


def shuffle03!(arr)
    len = arr.length
    for i in 0..len-1
        index1 = Random.rand(0..len-1)
        index2 = Random.rand(0..len-1)
        arr[index1], arr[index2] = arr[index2], arr[index1]
    end
end


arr = ['a', 'b', 'c', 'd']

st = ShuffleTest.new(arr)

for x in 0..100_0000
    shuffle03!(arr)
    st.test(arr)
end

st.show_count.each do |k, v|
    puts k
    p v
end

结果是:

a
[250418, 249105, 249553, 250925]
b
[249372, 250373, 250785, 249471]
c
[250519, 250097, 249369, 250016]
d
[249692, 250426, 250294, 249589]

看来是正确的。但是，我不知道如何用数理统计来证明它。所以我不确定它是否正确。

Answer 1

不，这是不对的。

假设您有一个四元素列表 [A,B,C,D]。观察到:

• 有 4 个! = 24 种可能的排列。要成为正确的洗牌算法，这些排列中的每一个都需要具有相同的可能性。
• 您要生成 4×2 = 8 个随机整数，每个整数都在 0–3 范围内，总共有 4⁸ = 65,536 个可能的随机数序列。这些序列中的每一个都有相同的可能性。
• 65,536 不能被 24 整除，因此您的算法无法将 65,536 个可能的随机数序列映射到排列，从而将相等数量的随机数序列(因此概率相等)分配给每个排列。

---

要在测试中看到这一点，您可以创建 shuffle03! 的一个变体，它不使用随机生成器，而是获取一个包含八个索引的列表，并使用它们。 (shuffle03! 然后可以通过生成八个随机索引然后将此变体调用为辅助函数来实现。)然后您的测试将遍历所有 4096 个可能的序列，并为每个序列创建一个四个- 元素列表 [A,B,C,D]，然后调用 variant 方法以查看生成的排列。该测试可以计算每个排列出现的频率，并使用它来找出哪些排列比其他排列出现的次数更多。你会发现:

 Permutation    # of Occurrences
-------------  ------------------
 A B C D                    4480
 A B D C                    3072
 A C B D                    3072
 A C D B                    2880
 A D B C                    2880
 A D C B                    3072
 B A C D                    3072
 B A D C                    2432
 B C A D                    2880
 B C D A                    2048
 B D A C                    2048
 B D C A                    2880
 C A B D                    2880
 C A D B                    2048
 C B A D                    3072
 C B D A                    2880
 C D A B                    2432
 C D B A                    2048
 D A B C                    2048
 D A C B                    2880
 D B A C                    2880
 D B C A                    3072
 D C A B                    2048
 D C B A                    2432

如您所见，元素往往以它们开始的相同顺序结束；例如，A B C D 是最常见的排列。我们可以通过查看每对元素以相同顺序与相反顺序结束的频率来得出这一点。我们发现:

 Elements    Same Order    Opposite Order
----------  ------------  ----------------
 A and B          33792             31744
 A and C          34816             30720
 A and D          35840             29696
 B and C          33792             31744
 B and D          34816             30720
 C and D          33792             31744

所以有些对比其他对更有可能以相反的顺序结束，但每一对更有可能以相同的顺序结束而不是以相反的顺序结束。

您可以通过执行更多遍来减少不平衡，但由于 8 的幂不能被 24 整除，因此永远不可能使所有排列的可能性相同。

---

顺便说一下，如果您的实际目标是一个好的随机播放算法(而不仅仅是自己找出一个的学习经验)，那么您应该使用 Fisher–Yates shuffle .

当然，由于您使用的是 Ruby，您可以通过使用 Array.shuffle! 来绕过整个问题，它会为您执行 Fisher–Yates 洗牌。