python 迭代中的数字排列

Question

我需要生成数字排列，数字可以大于数字计数。对于我目前的目的，我需要生成这些数字的排列 0, 1, 2 以获得最多 20 位数字的长度。例如，我的前几个排列是 0, 1, 2, 10, 11, 12, ... 1122, 1211.

在 Python here or here 中有使用迭代器的现有答案，这些答案直接给出了完整的排列。

但我需要对每个排列进行一些测试，如果我将整个排列列表保存在内存中，它会变得太大，尤其是对于 20 位数字，它会达到 3²⁰ 个排列.

所以我的问题是它是否可以不用递归来完成，这样我就可以对每个排列进行测试。

编辑:

我正在查看具有重复的排列。因此，对于 20 个数字，每个数字都可以从 [0, 1, 2] 中获取值。这就是为什么这种情况下的排列数会达到 3²⁰.

Answer 1

是的，您的程序可能是这样的：

import itertools


def perform_test(permutation):
    pass

# permutations() does not construct entire list, but yields 
# results one by on.
for permutation in itertools.permutations([1, 2, 3, 4, 5], 2):
    perform_test(permutation)

Answer 2

虽然有一些方法可以使用 itertools 等来执行此操作，但这里的方法与您通常使用的方法略有不同。

如果您要按顺序列出这些排列，您实际拥有的是代表它们在列表中位置的三进制数。例如list[4] 是 11，即三进制中的 4 (3*1+1*1)。因此，您可以将要测试的索引值转换为三进制，这将产生正确的值。

虽然 python 可以将整数转换为它在该基数中的形式（例如 int("11",3) 输出 4），但反向操作并未隐式实现。虽然有很多实现。 Here 是一个很好的（根据您的情况修改）：

def digit_to_char(digit):
    if digit < 10:
        return str(digit)
    return chr(ord('a') + digit - 10)

def perm(number):
    (d, m) = divmod(number, 3)
    if d > 0:
        return perm(d) + digit_to_char(m)
    return digit_to_char(m)

所以如果你想找到第 20 个排列，你可以执行 perm(20)，这会得到 202。所以现在你可以通过你想要的索引值进行常规循环。内存中没有存储大列表。

permutation = 0
i = 0
while len(str(permutation)) < 20:
    permutation = perm(i)
    do_test(permutation)
    i += 1

Answer 3

您正在寻找的是笛卡尔积，而不是排列。 Python itertools 有一个方法 itertools.product() 可以产生所需的结果：

import itertools

for p in itertools.product(range(3), repeat=4):
    print p

输出为 3^4 行：

(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 0, 2)
(0, 0, 1, 0)
(0, 0, 1, 1)
...
(2, 2, 2, 1)
(2, 2, 2, 2)

要生成长度为 1 到 4 的输出元组，请使用额外的迭代：

for l in range(1, 5):
    for p in itertools.product(range(3), repeat=l):
        print p

最后，这也适用于字符串元素：

for i in range(5):
    for p in itertools.product(('0', '1', '2'), repeat=i):
        print ''.join(p),
print

输出：

0 1 2 00 01 02 10 11 12 20 21 22 000 001 002 010 [...] 2220 2221 2222

python 迭代中的数字排列

Number permutations in python iterative

python

permutation