好些月前,前同事突然考我一个题目:怎么把一副牌打乱?
洗牌,说到底不就是数组元素打乱么?不假思索,我的第一想法就是,另起数组,然后通过随机数把原数组中元素一项一项的拿到新数组中。然而,稍微细想一番,这样子做的话肯定不是优解,其中一个瓶颈部分就在于,每次提取一个元素以后,我们都需要重新计算原始数组的剩余元素和长度,这明显会带来挺大的性能消耗。由此引发对洗牌程序的兴趣和学习。
# 洗牌准则
- 足够乱。
- 必定要有
n!
个结果。这个很好理解,假设有n
个数,最后的排列结果必定有n!
个。
# 思路
从低位 0 开始, 原始数组长度结束,进行遍历。每一个步骤都进行以下的操作:
- 获取从当前下标到数组最后值下标的随机整数。
- 交换当前下标和已得随机下标的值。
# 上代码
// 随机函数,或者 [min,max]中的任意整数
function randomIndex (min, max) {
max += 1
return Math.floor(Math.random() * (max - min) + min)
}
// 洗牌函数
function shuffle (sourceArr) {
const len = sourceArr.length
for (let i = 0; i < len; i ++) {
const rand = randomIndex(i, len - 1)
if(rand === i) continue
const item = sourceArr[rand]
sourceArr[rand] = sourceArr[i]
sourceArr[i] = item
}
return sourceArr
}
console.log(shuffle([1,2,3,4,5,6,7,8,9,10]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
其中,主要代码实现如下:
- 实现了一个
randomIndex
函数,主要负责返回从min
到max
中的随机整数。 - 实现一个
shuffle
洗牌程序, 内部逻辑就是获取从当前i
到 最后元素下标的随机整数,然后对换i
和 大于等于i
的随机整数下标
的值。直到遍历结束,确保所有的值都对换过。
# 对应准则
因为每次都是使用
Math.random
来随机获取下标值的,因此满足了足够乱的需求。由于每次对换的时候,
shuffle
中,与第i
(下标) 个元素对换的元素都有length - i
个可能,因此满足n!
的需求。
# 效果
由于本例是 javaScript 代码编写,因此代码可以直接放在浏览器控制台来查看结果。这里简单的验证一下:
# 总结
- 洗牌算法两大要求:一是要足够乱,二是结果集数量上是
n!
。 - 洗牌算法实现非常简单,基本思路就是遍历所有元素,通过当前元素与剩余随机下标(包含当前下标)的元素进行对换来完成。