CODEWITHSUNDEEP
pythonalgorithmperformanceoptimizationpython-itertools
user204452
user204452

Reputation: 21

How can I specify itertools permutations that only certain first combinations are allowed?

Question: How can I specify my itertools.permutations object so that it only contains permutations with one beginning that was given in a list? (Python 3.5)

The story: I have a puzzle, that has 36 puzzle elements, so theoretically 4e+41 possibilities. If I check this with itertools.permutations, it would calculate forever. Therefore I try to check which blocks fit in first place, and then only look for the second place with first places, that were possible.

e.g. block 2 doesn't fit in first place, then itertools.permutations(mylist,2) should no longer contain combinations like (2,1)(2,2)(2,3) etc.

mylist = [0,1,2,3]     # ..,34,35  - contains all puzzle blocks 
begin  = [(1,2),(1,3)] # this is the list of possible first blocks, so itertools should only give me combinations, that begin with one of this possibillities

combs = itertools.permutations(mylist,3) # --- THIS IS THE LINE OF THE QUESTION ---

At the moment, I do it using:

for thisposs in combs:
   if thisposs[0:2] in begin:
      checkblock(thisposs)       # check if thisposs is a combination that solves the puzzle

but this way the for loop still explodes. I want to specify the itertools object so that it doesn't have all possibilities but only those, that begin with something that is within the array/tuple/list:

begin = [(1,2),(1,3)]             # only one of these should be allowed in first two slots

This array is calculated again every time I increase one accuracy step, so during the optimization, it might take values like:

begin = [1,3,4,5,6]               # after permutations(mylist,1) - still a lot beginnings are possible
begin = [(1,6),(1,7),(5,1),(6,7)] # after permutations(mylist,2) - some combinations didn't work further
begin = [(5,1,2),(5,1,6),(5,1,7)] # after permutations(mylist,3) - the solution can for sure only begin with 5-2-???
# and so on

Every time I made one "accuracy step", I make a new itertools object with

combs = itertools.permutations(mylist,n+1)

So my question is: How can I specify my itertools.permutations object so that it only contains permutations with one beginning that was given in a list?

Upvotes: 2

Views: 992

Answers (1)

Scott Mermelstein
Scott Mermelstein

Reputation: 15397

At any level, you want to have a function that looks at each begin sequence, removes the elements of the begin sequence from the set of possibilities, and then permutes the remainder.

Here's a generator that will do that:

def find_permutations(begin_sequences, full_set):
    for begin_sequence in begin_sequences:
        remaining_set = full_set - set(begin_sequence)
        for ending in itertools.permutations(remaining_set):
            yield begin_sequence + list(ending)

If you want to try this with your 1st example, try this. (Note that if you do print this out, since you're full_set is so big, you may be there awhile. You may want to reduce it to something like 8 for testing purposes.):

full_set = set(range(1,37))
for p in find_permutations([[1], [3], [4], [5], [6]], full_set):
    print(p)

Your final example would go like this:

for p in find_permutations([[5,1,2], [5,1,6], [5,1,7]], full_set):
    print(p)

Upvotes: 1

Related Questions