如何有效地创建对特定字符有限制的排列？

Question

让您了解我在说什么。这是我现在的代码：

chrs = 'ABCDEF1234567890'
with open('two.txt', 'w') as two:
    for xs in itertools.product(chrs, repeat=10):
        h = sum(x.isalpha() for x in xs)
        if h == 2: two.write(''.join(xs) + '\n')

不幸的是，这实际上需要几天时间，因为它会创建所有可能的组合，其中大部分都不匹配。

编辑：为了澄清，我需要一种方法来找到变量 chrs 的所有可能组合，其中只有两个字母（'ABCDEF'）。无需创建所有组合的完整列表并检查每个组合。我只需要创建其中包含两个字母的那些。

更进一步：

'AA12345678' = Good
'1234A123A4' = Good
'AAA1234567' = Bad
'A123456789' = Bad

我真的不知道仅仅 5 行 python 代码我还能解释多少。

Answer 1

嗯，它只是从 0x0 到 0x10000000000 的十六进制数。不幸的是，这是十进制的 ~1.75e13，所以如果每个字符是 1 个字节并且每个字符串是 10 个字符，那么如果不进行过滤，你的 two.txt 的大小将是 175TB。

一旦你这样想，应该有一些方法可以通过一些简单的模数运算快速剔除列表中的大片区域，这将是我要走的路。

Answer 2

这是基于 stars and bars 而不是组合和排列。

从标准星条算法开始，的改进：

def stars_and_bars(star='*', bar='|', star_count=8, bar_count=2):
    if star_count == 0:
        yield (bar,) * bar_count
        return
    if bar_count == 0:
        yield (star,) * star_count
        return
    for left in range(star_count + 1):
        right = star_count - left
        assert right >= 0
        assert left + right == star_count
        for partial in stars_and_bars(star, bar, left, bar_count - 1):
            yield partial + (bar,) + (star,) * right

验证它是否有效：

>>> sandb = stars_and_bars(star_count=3, bar_count=2)
>>> for result in sandb:
...     print(''.join(result))
... 
||***
|*|**
*||**
|**|*
*|*|*
**||*
|***|
*|**|
**|*|
***||

如您所见，这会生成星形和条形的各种可能排列。有了 8 颗星和两个条，我们可以用它来找到所有可能的数字和字母排列。然后我们将其传递给 itertools.product():

def combos():
    letters = 'ABCDEF'
    numbers = '1234567890'
    argument_combos = stars_and_bars(numbers, letters)
    for args in argument_combos:
        yield from itertools.product(*args)

结果将完全符合 OP 的要求。

Answer 3

我投了赞成票 by Kevin，但我仍然觉得他的 stars_and_bars 实施有点过头了...这是我的看法

我的天啊，复制粘贴错误...一个括号下移了一行...

~~$ cat starbar.py from itertools import combinations as _ic_ def sb(s, ns, b, nb): l = list(range(nb+ns) ---------------V return ([b if i in k else s for i in l)]for k in _ic_(l, nb))~~

现在这是正确的版本

$ cat starbar.py
from itertools import combinations as _ic_
def sb(s, ns, b, nb):
    l = list(range(nb+ns))
    return ([b if i in k else s for i in l] for k in _ic_(l, nb))

或者，如果您喜欢冗长的名称，

from itertools import combinations
def stars_and_bars(star, number_of_stars, bar, number_of_bars):
    possible_positions = list(range(number_of_bars + number_of_stars))
    return ([bar if i in combination else star for i in l]
            for combination in combinations(possible_positions, number_of_bars))

它是如何工作的？要修复这些想法，请说 ns, nb = 2, 3 并查看 itertools.combination

所做的事情

>>> list(itertools.combinations(range(ns+nb),nb))
[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

你有一个迭代器，其中包含 [0,1,2,3,4] 中 3 个不同数字的所有可能的有序选择，此时很容易 return 包含的列表正确的星条顺序

>>> from starbar import sb
>>> for s_b in sb('*',2, '|',3): print ''.join(s_b)
...
|||**
||*|*
||**|
|*||*
|*|*|
|**||
*|||*
*||*|
*|*||
**|||
>>>

如何有效地创建对特定字符有限制的排列？

How can i create a permutation with a limit on specific characters efficently?

python

itertools