如何使用Pythonitertools.product()引入约束？

Question

以下脚本生成集合 s 的 4 个字符排列并输出到文件：

import itertools


s = ['1', '2', '3', '4', '!']

l = list(itertools.product(s, repeat=4))

with open('output1.txt', 'w') as f:
    for i in l:
        f.write(''.join([str(v) for v in i]) + '\n')

输出：

...
11!1
11!2
11!3
11!4
11!!
...

约束是如何引入的如：

任何排列都不应以 '!'
第三个字符应该是'3'
等等

Answer 1

不要将结果转换为列表。相反，使用生成器理解来过滤它：

result = itertools.product(s, repeat=4)
result = (''.join(word) for word in result)
result = (word for word in result if not word.startswith('!'))
result = (word for word in result if word[2] == '3')

直到你真正从result中读取元素才会执行过滤，例如将其转换为列表或使用for循环：

def f1(x):
    print("Filter 1")
    return x.startswith('A')
    
def f2(x):
    print("Filter 2")
    return x.endswith('B')
    
words = ['ABC', 'ABB', 'BAA', 'BBB']

result = (word for word in words if f1(word))
result = (word for word in result if f2(word))
print('No output here')

print(list(result))
print('Filtering output here')

这将输出

No output here
Filter 1
Filter 2
Filter 1
Filter 2
Filter 1
Filter 1
['ABB']
Filtering output here

Answer 2

itertools.product 函数无法处理您描述的各种约束。不过，您可以通过额外的迭代和更改构建输出的方式来自己实现它们。例如，要生成一个 4 字符的字符串，其中第三个字符始终为 3，请生成一个 3-product 并用它来填充第一个、第二个和第四个字符，而第三个字符保持不变。

这是针对您的两个建议约束的解决方案。这里并没有真正的概括，我只是解释每一个并将它们结合起来：

import itertools

s = ['1', '2', '3', '4', '!']

for i in s[:-1]: # skip '!'
    for j, k in itertools.product(s, repeat=2): # generate two more values from s
        print(f'{i}{j}3{k}')

此方法避免生成需要过滤掉的值。这比生成所有可能的四元组并过滤掉违反约束的四元组效率高很多。过滤方法通常会做很多倍的工作，而且你拥有的约束越多，它就会按比例变得越糟（因为越来越多的生成值将被过滤）。

Answer 3

Itertools 的产品没有集成过滤机制。它会粗暴地生成所有排列，你将不得不过滤它的输出（这不是很有效）。

为了提高效率，您需要实现自己的（递归）生成器函数，以便您可以在不满足其中一个约束条件时（即在进行完整排列之前）立即短路生成：

def perm(a,p=[]):
    # constraints applied progressively
    if p and p[0] == "!": return
    if len(p)>= 3 and p[2]!= '3': return
    
    # yield permutation of 4
    if len(p)==4: yield p; return
    
    # recursion (product)
    for x in a:
        yield from perm(a,p+[x])

输出：

s = ['1', '2', '3', '4', '!']
for p in perm(s): print(p)
        
['1', '1', '3', '1']
['1', '1', '3', '2']
['1', '1', '3', '3']
['1', '1', '3', '4']
['1', '1', '3', '!']
['1', '2', '3', '1']
['1', '2', '3', '2']
['1', '2', '3', '3']
...
['4', '4', '3', '3']
['4', '4', '3', '4']
['4', '4', '3', '!']
['4', '!', '3', '1']
['4', '!', '3', '2']
['4', '!', '3', '3']
['4', '!', '3', '4']
['4', '!', '3', '!']

Answer 4

repeat 参数用于当您想要序列中每个位置的相同选项集时使用。既然你不这样做，那么你应该只使用位置参数来为序列中的每个位置提供选项。 (docs link)

对于你的例子，第一个字母可以是['1', '2', '3', '4']中的任意一个，第三个字母只能是'3':

import itertools as it

s = ['1', '2', '3', '4', '!']
no_exclamation_mark = ['1', '2', '3', '4']
only_3 = ['3']

l = it.product(no_exclamation_mark, s, only_3, s)

@Kelly Bundy 在评论中写了相同的解决方案，但使用字符串是字符序列这一事实进行了简化，因此如果每个位置的选项每个都只有一个字符，则无需将它们放入列表：

l = it.product('1234', '1234!', '3', '1234!')

如何使用Pythonitertools.product()引入约束？

How to introduce constraints using Python itertools.product()?

python

combinatorics

itertools

more-itertools