查找长度正好为 9 个字符的数字的所有排列

Question

我有号码[0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16]。

我想找出恰好 9 个字符的数字的所有排列。比如我有8个个位数，最后一个不能是双位数，因为会超出字符数限制。

澄清：

相同的数字可以重复使用，例如数字 1 九次有效。
两位数可以是任意个数，只要数字的总字符长度正好为9即可。例如1、10、12、15、16都是有效的。

我试过 itertools.permutations，但无法使用两位数。

Answer 1

注意：这比需要的慢得多。

一种简单的、性能不佳的蛮力过滤方法：

symbols = [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16]
symbols = [str(x) for x in symbols]
perms = itertools.chain.from_iterable(
    itertools.permutations(symbols, i) for i in range(10)
)
perms = ("".join(x) for x in perms)
perms = [x for x in perms if len(x) <= 9]

>>> len(perms)
13600046

>>> perms[:4]
['', '0', '1', '2']

>>> perms[-4:]
['987643102', '987643120', '987643201', '987643210']

只需跳过 perms 中的第一项即可删除空字符串。

不使用字符串的类似方法：

symbols = [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16]
lengths = {k: int(math.log10(k)) + 1 if k != 0 else 1 for k in symbols}
perms = itertools.chain.from_iterable(
    itertools.permutations(symbols, i) for i in range(10)
)
perms = [x for x in perms if sum(lengths[k] for k in x) <= 9]

>>> len(perms)
13600046

如果数字可以重复使用（如评论中所述），我会考虑 itertools.product 而不是 itertools.permutations:

symbols = [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16]
lengths = {k: int(math.log10(k)) + 1 if k != 0 else 1 for k in symbols}
perms = itertools.product(symbols, repeat=9)
perms = [x for x in perms if sum(lengths[k] for k in x) <= 9]

Answer 2

我会混合使用组合和排列。

首先找到所有加起来达到所需长度的数据组合。然后对于每个独特的组合，找到它们的排列。这里可能有一些工作要做，可以限制检查的不正确组合的数量：

import itertools


def perm_of_length(data, length):
    for i in range(len(data)):
        for comb in itertools.combinations(data, i + 1):
            if sum(map(len, (map(str, comb)))) == length:
                for perm in itertools.permutations(comb):
                    yield perm


for perm in perm_of_length([0, 1, 2, 3, 10, 12], 4):
    print(perm)

输出：

(10, 12)
(12, 10)
(0, 1, 10)
(0, 10, 1)
(1, 0, 10)
(1, 10, 0)
(10, 0, 1)
(10, 1, 0)
(0, 1, 12)
(0, 12, 1)
(1, 0, 12)
(1, 12, 0)
(12, 0, 1)
(12, 1, 0)
(0, 2, 10)
(0, 10, 2)
(2, 0, 10)
(2, 10, 0)
(10, 0, 2)
(10, 2, 0)
(0, 2, 12)
(0, 12, 2)
(2, 0, 12)
(2, 12, 0)
(12, 0, 2)
(12, 2, 0)
(0, 3, 10)
(0, 10, 3)
(3, 0, 10)
(3, 10, 0)
(10, 0, 3)
(10, 3, 0)
(0, 3, 12)
(0, 12, 3)
(3, 0, 12)
(3, 12, 0)
(12, 0, 3)
(12, 3, 0)
(1, 2, 10)
(1, 10, 2)
(2, 1, 10)
(2, 10, 1)
(10, 1, 2)
(10, 2, 1)
(1, 2, 12)
(1, 12, 2)
(2, 1, 12)
(2, 12, 1)
(12, 1, 2)
(12, 2, 1)
(1, 3, 10)
(1, 10, 3)
(3, 1, 10)
(3, 10, 1)
(10, 1, 3)
(10, 3, 1)
(1, 3, 12)
(1, 12, 3)
(3, 1, 12)
(3, 12, 1)
(12, 1, 3)
(12, 3, 1)
(2, 3, 10)
(2, 10, 3)
(3, 2, 10)
(3, 10, 2)
(10, 2, 3)
(10, 3, 2)
(2, 3, 12)
(2, 12, 3)
(3, 2, 12)
(3, 12, 2)
(12, 2, 3)
(12, 3, 2)
(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)

证明这是有效的：

for perm in perm_of_length([0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16], 9):
    assert sum(map(len, map(str, perm))) == 9

查找长度正好为 9 个字符的数字的所有排列

Find all permutations of numbers of exactly 9 characters long

python

permutation