这个混乱算法对吗？

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 shuffle.