python实现三种洗牌算法

Algorithms

这个题来源于前一段时间同事的面试题，众所周知平时对于排序是考察比较多的，洗牌算法（打乱算法）是他的逆过程。从种类来看，洗牌算法大致分为三种：

Fisher-Yates Shuffle

思想就是从原始数据随机抽取一个新的数字到新数组中，python实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
 1. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k]之间的数字p（假设数组从0开始）；
 2. 从剩下的k个数中把第p个数取出；
 3. 重复步骤2和3直到数字全部取完；
 4. 从步骤3取出的数字序列便是一个打乱了的数列。
'''
import random

def fisher_yates_shuffle(list):
    # apply for a new list
    res = []
    while list:
        p = random.randrange(0, len(list))
        res.append(list[p])
        list.pop(p)
    return res
    
r = fisher_yates_shuffle([1, 2, 2, 3, 3, 4, 5, 10])
print(r)

Knuth-Durstenfeld Shuffle

Knuth将Fisher算法加以改进。每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的末尾，即数组尾部存放的都是处理过的数据。Knuth是一个原地打乱的算法。

1
2
3
4
5
6
7
8
9
10
11
import random

def knuth_shuffle(list):
    # no extra space
    for i in range(len(list) - 1, 0, -1):
        p = random.randrange(0, i + 1)
        list[i], list[p] = list[p], list[i]
    return list
    
r = knuth_shuffle([1, 2, 2, 3, 3, 4, 5, 10])
print(r)

Inside-Out Algorithm

Knuth算法是一个in-place算法，原始数据被直接打乱，但有些情形下需要保存原始数据，因此需要重新开辟一个新数组来存储打乱后的序列。Inside-Out算法的基本思想是设置一个游标 i 从前向后扫描原始数据的拷贝，在[0, i]之间随机一个下标 j，然后用位置 j 的元素替换掉位置 i 处的数字，再用原始数据位置 i 的元素替换掉拷贝数据位置 j 的元素。作用相当于在拷贝数据中交换位置 i 和 j 处的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
import random

def inside_out_shuffle(list):
    # save original data
    res = list[:]
    for i in range(1, len(list)):
        j = random.randrange(0, i)
        res[i] = res[j]
        res[j] = list[i]
    return res
    
r = inside_out_shuffle([1, 2, 2, 3, 3, 4, 5, 10])
print(r)

后记

前面使用python实现了三种洗牌算法，其实python的random模块也提供了shuffle的方法，用法如下：

1
2
3
4
5
>>> import random
>>> items = [1, 2, 3, 4, 5, 6, 7]
>>> random.shuffle(items)
>>> items
[7, 4, 5, 6, 1, 2, 3]

其内部正是使用的Knuth的Shuffle算法。