如何使用Python itertools.product()引入约束



以下脚本生成集合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'
  • 等等

repeat参数是指当您希望序列中的每个位置都有相同的选项集时使用的。既然没有,那么就应该使用位置参数来为序列中的每个位置提供选项。(文档链接(

例如,第一个字母可以是['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!')
不要将结果转换为列表。相反,使用生成器理解进行过滤:
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

itertools.product函数无法处理您自己描述的约束类型。不过,您可能可以通过额外的迭代和对构建输出方式的更改来自己实现它们。例如,要生成第三个字符始终为3的4个字符的字符串,请生成一个3乘积,并用它填充第一个、第二个和第四个字符,使第三个固定不变。

以下是您建议的两个约束条件的解决方案。这里并没有真正的概括,我只是解释每一个并将其组合:

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}')

这种方法避免生成需要过滤掉的值。这比生成所有可能的四个元组并过滤违反约束的元组要高效得多。过滤方法通常会做很多倍的工作,而且约束越多,情况就越糟(因为会过滤越来越多生成的值(。

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', '!']

最新更新