时间戳

首页 > 解决方案 > 在 Python 中生成唯一排列的最佳方法是什么？

python - 在 Python 中生成唯一排列的最佳方法是什么？

问题描述

对于每个项目，我有 0 和 1 之间的 2 个选择，其中我将有 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循环。

有没有更聪明或更优雅的方法来做到这一点？

标签： pythonrandomcombinationssequencecombinatorics

解决方案

  • 这是一个二进制数，每个唯一的二进制数对应一个唯一的十进制数。
  • 有 10 个地方，有 2^10 = 1024 个唯一的。
  • 从这 1024 中选择 10 无需更换
  • 将十进制转换为二进制

生成 5 个唯一样本，每个样本 10 位

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(" ", "")

推荐阅读