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

Question

The following script generates 4-character permutations of set s and outputs to file:

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

Output:

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

How are constraints introduced such as:

• No permutation should start with '!'
• The 3rd character should be '3'
• etc.

Answer 1

The repeat parameter is meant to be used when you do want the same set of options for each position in the sequence. Since you don't, then you should just use positional arguments to give the options for each position in the sequence. (docs link)

For your example, the first letter can be any of ['1', '2', '3', '4'], and the third letter can only be '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 wrote the same solution in a comment, but simplified using the fact that strings are sequences of characters, so if your options for each position are just one character each then you don't need to put them in lists:

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

Answer 2

Don't convert the result to a list. Instead, filter it using a generator comprehension:

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

The filtering will not be executed until you actually read the elements from result, such as converting it to a list or using a for-loop:

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

This will output

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

Answer 3

The itertools.product function can't handle the kinds of constraints you describe itself. You can probably implement them yourself, though, with extra iteration and changes to how you build your output. For instance, to generate a 4-character string where the third character is always 3, generate a 3-product and use it to fill in the first, second and fourth characters, leaving the third fixed.

Here's a solution for your two suggested constraints. There's not really a generalization to be made here, I'm just interpreting each one and combining them:

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

This approach avoids generating values that will need to be filtered out. This is a lot more efficient than generating all possible four-tuples and filtering the ones that violate the constraints. The filtering approach will often do many times more work, and it gets proportionally much worse the more constraints you have (since more and more of the generated values will be filtered).

Answer 4

Itertools' product does not have an integrated filter mechanism. It will generate all permutations brutally and you will have to filter its output (which is not very efficient).

To be more efficient you would need to implement your own (recursive) generator function so that you can short-circuit the generation as soon as one of the constraint is not met (i.e. before getting to a full permutation):

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])

Output:

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