在 Python 中生成唯一排列的最佳方法是什么?
What's the best way to generate unique permutations in Python?
对于每个项目,我有 2 个 0 和 1 之间的选择,其中我将 N 个元素一个接一个地排序,生成一个唯一的组合。
所以像这样(序列长度=10):
0, 1, 0, 1, 0, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 1, 0, 1, 0, 1
0, 1, 1, 1, 0, 1, 0, 1, 0, 1
1, 1, 1, 1, 0, 1, 0, 1, 0, 1
如您所见,这些都是独特的排列。我将有 10000 个这样的排列(例如)。但关键信息是我不需要所有的排列,而是只保存有限的一组排列,最好是无序的,所以它更“随机”一点。
我目前的解决方案是生成介于 0 和 1 之间的随机数,并将它们附加到最多 N 个元素的数组中。然后将此数组转换为字符串,如果此字符串尚未添加到我上面的列表中,则添加此字符串,否则重复相同的步骤以生成不同的排列。
所以这意味着使用 while 循环。
有没有更聪明、更优雅的方法来做到这一点?
- 这是一个二进制数,每个唯一的二进制数对应一个
唯一小数。
- 有 10 个地方,有 2^10 = 1024 个唯一。
- 从这1024个中选出10个不放回
- 将十进制转换为二进制
每 10 个数字生成 5 个唯一样本
import numpy as np
n_digits = 10
n_sample = 5
for c in np.random.choice(np.power(2,n_digits), size=n_sample, replace=False):
c = int("{0:b}".format(c))
print (str(c).zfill(n_digits))
样本运行
0100011110
0110110011
0100110001
1110011100
1110101011
编辑:
上面的代码速度很快,但由于 np.power(2,n_digits)
会导致溢出,因此无法扩展到更大的数字 np.random.choice
将 运行 内存不足。
为了将它扩展到非常大的序列,我们可以使用有点慢但非常不错的机制,如下所示
n_digits = 200
n_sample = 10000
choices = []
cache = {}
while len(choices) < n_sample:
c = np.random.randint(0,2,(n_digits))
k = c.tostring()
if not k in cache:
cache[k] = True
choices.append(c)
%timeit
返回
27.4 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
相当不错。
choices
是 numpy 数组的列表,如果你想将它转换成文本,你可以使用
for i in range(len(choices)):
choices[i] = np.array2string(choices[i], separator='')[1:-1].replace("\n", "").replace(" ", "")
对于每个项目,我有 2 个 0 和 1 之间的选择,其中我将 N 个元素一个接一个地排序,生成一个唯一的组合。
所以像这样(序列长度=10):
0, 1, 0, 1, 0, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 1, 0, 1, 0, 1
0, 1, 1, 1, 0, 1, 0, 1, 0, 1
1, 1, 1, 1, 0, 1, 0, 1, 0, 1
如您所见,这些都是独特的排列。我将有 10000 个这样的排列(例如)。但关键信息是我不需要所有的排列,而是只保存有限的一组排列,最好是无序的,所以它更“随机”一点。
我目前的解决方案是生成介于 0 和 1 之间的随机数,并将它们附加到最多 N 个元素的数组中。然后将此数组转换为字符串,如果此字符串尚未添加到我上面的列表中,则添加此字符串,否则重复相同的步骤以生成不同的排列。
所以这意味着使用 while 循环。
有没有更聪明、更优雅的方法来做到这一点?
- 这是一个二进制数,每个唯一的二进制数对应一个 唯一小数。
- 有 10 个地方,有 2^10 = 1024 个唯一。
- 从这1024个中选出10个不放回
- 将十进制转换为二进制
每 10 个数字生成 5 个唯一样本
import numpy as np
n_digits = 10
n_sample = 5
for c in np.random.choice(np.power(2,n_digits), size=n_sample, replace=False):
c = int("{0:b}".format(c))
print (str(c).zfill(n_digits))
样本运行
0100011110
0110110011
0100110001
1110011100
1110101011
编辑:
上面的代码速度很快,但由于 np.power(2,n_digits)
会导致溢出,因此无法扩展到更大的数字 np.random.choice
将 运行 内存不足。
为了将它扩展到非常大的序列,我们可以使用有点慢但非常不错的机制,如下所示
n_digits = 200
n_sample = 10000
choices = []
cache = {}
while len(choices) < n_sample:
c = np.random.randint(0,2,(n_digits))
k = c.tostring()
if not k in cache:
cache[k] = True
choices.append(c)
%timeit
返回
27.4 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
相当不错。
choices
是 numpy 数组的列表,如果你想将它转换成文本,你可以使用
for i in range(len(choices)):
choices[i] = np.array2string(choices[i], separator='')[1:-1].replace("\n", "").replace(" ", "")