P125: Generate a random permutation of the elements of a list
生成列表元素的随机排列。一个长度为n
的列表的随机排列有n!
种可能,「用枚举法构造所有可行解的集合,再判断实际解是否属于可行解集合」这种方法实在是太恶心了。其实,祇要一个列表满足以下三个条件,它就属于可行解集合了:
- 长度等于原列表长度
- 列表内元素没有重复
- 列表内每一个元素都属于原列表
完整的测试用例:
from python99.lists.p125 import rnd_permu
import functools
import operator
def test_rnd_permu():
l = [e for e in range(1, 11)]
actual = rnd_permu(l)
assert len(actual) == len(l)
assert set(actual) == set(l)
assert functools.reduce(operator.and_, [e in l for e in actual], True)
之前,我们在random.sample
的帮助下,实现了「从长度为M的列表中随机抽取N个元素」。当M等于N时,random.sample
就等于是随机排列列表中的元素了。
代码实现:
# Generate a random permutation of the elements of a list.
# Hint: Use the solution of problem 1.23
import random
def rnd_permu(l):
return random.sample(l, len(l))