我正在寻找一种随机采样所有排列的固定长度子集的方法。
import itertools
from random import shuffle
mylist = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T']
方法A
下面的方法A存在排列过于相似的问题。
a_pre = itertools.permutations(mylist,20)
a = itertools.islice(a_pre,3)
list(a)
["A"、"B"、"C"、"D"、"E"、"F"、"G"、"H"、"I"、"J"、"K"、"L"、"M"、"N"、"O"、"P"、"Q"、"R"、"S"、"T"]
["A"、"B"、"C"、"D"、"E"、"F"、"G"、"H"、"I"、"J"、"K"、"L"、"M"、"N"、"O"、"P"、"Q"、"R"、"T"、"S"]
["A"、"B"、"C"、"D"、"E"、"F"、"G"、"H"、"I"、"J"、"K"、"L"、"M"、"N"、"O"、"P"、"Q"、"S"、"R"、"T"]
方法B
方法 B 使我更接近我想要的结果,但在这里总是存在在列表之间产生相同排序的风险,因此这种方法不可行。
#repeat n=3 times
shuffle(mylist)
print(mylist)
["J"、"B"、"M"、"A"、"O"、"C"、"K"、"S"、"H"、"Q"、"N"、"T"、"R"、"D"、"G"、"P"、"I"、"E"、"F"、"L"]
["R"、"O"、"C"、"I"、"G"、"E"、"Q"、"L"、"P"、"J"、"F"、"N"、"A"、"B"、"H"、"T"、"D"、"K"、"M"、"S"]
["L"、"O"、"I"、"G"、"B"、"E"、"R"、"A"、"D"、"N"、"J"、"S"、"H"、"F"、"K"、"M"、"Q"、"T"、"C"、"P"]
但这里总是存在在列表之间产生相同排序的风险,因此这种方法不可行。
您可以使用元组(因为列表不可哈希)和集合(这样就不会有重复/相同的列表)来解决这个问题:
from random import shuffle
mylist = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T']
myset = set()
while len(myset) < 5: #change 5 to however many you want
shuffle(mylist)
myset.add(tuple(mylist))
print([list(x) for x in myset])
编辑:正如@tobias_k指出的那样:
对于给定的列表,有 20! = 2432902008176640000种不同的排列,因此碰撞的可能性很小。
考虑迭代工具random_permutation
配方:
从文档中:
def random_permutation(iterable, r=None):
"Random selection from itertools.permutations(iterable, r)"
pool = tuple(iterable)
r = len(pool) if r is None else r
return tuple(random.sample(pool, r))
法典
import string
import more_itertools as mit
iterable = string.ascii_uppercase[:-6]
[random_permutation(iterable) for _ in range(3)]
输出
[('M', 'K', 'Q', 'A', 'I', 'J', 'H', 'T', 'C', 'E', 'P', 'L', 'B', 'N', 'G', 'F', 'S', 'D', 'O', 'R'),
('A', 'G', 'I', 'S', 'E', 'T', 'B', 'Q', 'D', 'M', 'C', 'O', 'J', 'H', 'N', 'F', 'K', 'P', 'R', 'L'),
('C', 'S', 'O', 'H', 'I', 'K', 'A', 'G', 'D', 'B', 'R', 'E', 'L', 'T', 'M', 'N', 'F', 'P', 'Q', 'J')]
more_itertools
是为您实现此配方的第三方库。
您可以使用它来生成N
元素的第number
字典目录:
def permutation_from_int(N, number):
'''
get the number-th lexicographic permutation of length N.
N: the length of the permutation
0 <= number <= factorial(N) -1: the number of the desired
permutation
'''
# assert 0 <= number < factorial(N)
ret = [None] * N
select = list(range(N))
for i in range(N - 1, -1, -1):
index, number = divmod(number, factorial(i))
element = select[index]
ret[N - 1 - i] = element
select.remove(element)
return ret
然后,您只需要生成(并保留set
- 如果您想避免重复)表示排列的随机整数:
N_TESTS = 17
strg = 'ABCD'
N = len(strg)
N_MAX = factorial(N)
seen = set()
for _ in range(N_TESTS):
number = randrange(N_MAX)
while number in seen:
number = randrange(N_MAX)
seen.add(number)
perm = permutation_from_int(N, number)
print(''.join(strg[i] for i in perm))
请注意,如果测试的数量大于所有排列的空间,这可能会永远循环......
打印(例如):
DACB
DBCA
BADC
BDCA
DCAB
DABC
CADB
DBAC
DCBA
...
但正如其他答案中提到的:如果你有 20 个元素的排列,那么达到重复排列的机会非常小!
我认为你的问题是我遇到的一个特例,因为 k=N 基于此,应适用其中所述的两种解决方案。第一个有点慢:)
所以随机抽样(你也暗示了你的问题,只是丢弃重复项......)似乎是目前唯一的答案。
看看这个问题是否有生成解决方案或更普遍的解决方案会非常有趣...... 以下是基于该答案的代码:
import itertools
from random import shuffle
mylist = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T']
n=len(mylist)
k = n
m = 5
samples = set()
tries = 0
while len(samples) < m:
samples.add(tuple(random.sample(mylist,k)))
print (len(samples))
print(samples)
print(tries)