对于算法书买了一本又一本却没一本读完超过 10%,Leetcode 刷题从来没坚持超过 3 天的我来说,算法能力真的是渣渣。但是,今天决定写一篇跟算法有关的文章。起因是读了吴师兄的文章《扫雷与算法:如何随机化的布雷(二)之洗牌算法》。因为扫雷这个游戏我是写过的,具体见:《Python:游戏:扫雷》。
游戏开始的时候需要随机布雷。扫雷的高级是 16 × 30 的网格,一共有 99 个雷。如果从 0 开始给所有网格做标记,那么布雷的问题就成了从 480 个数中随机选取 99 个数。
第一反应自然是记录已选项:
import random
mines = set()
for i in range(99):
j = random.randint(0, 480)
while j in mines:
j = random.randint(0, 480)
mines.add(j)
print(mines)
不过这算法看着似乎有点 low 啊。
其实从 480 个数中随机抽取 99 个数,那么只要将这 480 个数打乱,取前 99 个数就好了。这就引出了:高纳德置乱算法(洗牌算法)。
这个算法很牛逼却很好理解,通俗的解释就是:将最后一个数和前面任意 n-1 个数中的一个数进行交换,然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换……以此类推。
这个原理很好理解,通俗得不能再通俗,稍微想一下就会明白,确实如此。
洗牌算法的 Python 实现如下:
import random
lst = list(range(10))
for i in reversed(range(len(lst))):
j = random.randint(0, i)
lst[i], lst[j] = lst[j], lst[i]
print(lst)
看了吴师兄的文章,我立马去翻了我的扫雷代码,我觉得,我一定是用的那个很 “low” 的算法。翻出代码一看,我用的是 Python 提供了随机取样算法:random.sample
,感叹 python 的强大,这都有。然后我就想到了,随机打乱一个序列,random.shuffle
不就是干这事的吗?那么 random.shuffle
会是用的洗牌算法吗?
翻看 random.shuffle
的源码,发现正是洗牌算法。
def shuffle(self, x, random=None):
if random is None:
randbelow = self._randbelow
for i in reversed(range(1, len(x))):
j = randbelow(i + 1)
x[i], x[j] = x[j], x[i]
else:
_int = int
for i in reversed(range(1, len(x))):
j = _int(random() * (i + 1))
x[i], x[j] = x[j], x[i]
一切都是如此的自然而美好,然后我又去瞄了一眼 random.sample
的源码,然后就一头雾水了。我截了部分源码:
n = len(population)
result = [None] * k
setsize = 21 # size of a small set minus size of an empty list
if k > 5:
setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
if n <= setsize:
# An n-length list is smaller than a k-length set
pool = list(population)
for i in range(k):