一日一技：如何手动打乱一个列表

摄影：产品经理

产品经理亲手做的法式香煎鹅肝

我们知道，在 Python 里面，可以使用 random.shuffle打乱一个列表，如下图所示：

那么，如果我们要自己写一个打乱列表的算法，应该怎么写呢？

我们可以使用Fisher–Yates shuffle[1] 算法。这个算法的基本思想是：

1. 从列表中任选一个数字，把它跟最后一个数字交换。
2. 从列表索引为0-(n-2)中任选一个数字，把它和倒数第二位交换。
3. 从列表索引为0-(n-3)位中，任选一个数字，把它和倒数第三位交换。
4. …
5. 从索引为0，1中任选一个数字，把它和索引为1的数字交换。

具体的代码实现非常简单：

import random

def shuffle(target):
    for change in range(len(target) - 1, 0, -1):
        lower = random.randint(0, change)
        target[lower], target[change] = target[change], target[lower]

这个一个 in-place操作，直接修改原列表，所以不需要返回。

运行效果如下图所示：

每次运行，它的结果都是不一样的。

参考资料

[1]

Fisher–Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle