How to recursively create a list of permutations in python?

Question

I have a dictionary called possibilities where the key is an index and the values for that key are the values that can sit on that index in a list. See below:

possibilities = {0: [None, 'KLAX_1', 'KDEN_1'],
 1: [None, 'KLAX_1', 'KDEN_1'],
 2: [None, 'KLAX_1', 'KLAS_1', 'KDEN_1'],
 3: [None, 'KLAX_1', 'KLAS_1', 'KPHX_1', 'KDEN_1', 'KDFW_1'],
 4: [None, 'KPHX_1', 'KDEN_2', 'KDFW_2'],
 5: [None, 'KDEN_2', 'KDFW_2'],
 6: [None, 'KDEN_2']}

I want to save every permutation of this list in another list called permutations_list. My goal is to create this permutations_list from the possibilities dict. Currently I have a huge nested for loop that builds this (see below). But I want to have a function that takes in the possibilities_dict and generates my list automatically. I'm thinking that a recursive function will allow me to not specify the number of indexes I need.

for index_0 in possibilities[0]:
    for index_1 in possibilities[1]:
        for index_2 in possibilities[2]:
            for index_3 in possibilities[3]:
                for index_4 in possibilities[4]:
                    for index_5 in possibilities[5]:
                        for index_6 in possibilities[6]:
                            lst = [index_0,index_1,index_2,index_3,index_4,index_5,
                                  index_6]
                            permutations_list.append(lst)

The result from the code above is a list permutations_list of length 5184. Each item in that list is a list that contains a specific permutation of all the values. This is not as simple as using itertools.permutations as only specific values can sit at specific indexes on the list. Can anyone help provide a recursive function for doing this? Thanks.

What you need is simply `itertools.product` for a cartesian product. — blhsing, Oct 09 '19 at 01:32
Please study what `itertools.product` does first and then ask specific questions regarding its usage if you still don't see how you can apply it to your question. There are numerous examples on stackoverflow.com. — blhsing, Oct 09 '19 at 01:43
"But I want to do this recursively." No, you don't want to do it recursively. You just don't know that yet. — Klaus D., Oct 09 '19 at 03:01
Thanks @blhsing I have tried it and it works! BUT, it gives me back a list of tuples whereas I want a list of lists. Also I have to manually input my iterables in the product() function. Which is a pain as I plan to expand my scale so I would have to put in product(A,B,C,D,....K) etc — azizbro, Oct 09 '19 at 03:01
@Azizbro Here's an example: https://stackoverflow.com/questions/3034014/how-to-apply-itertools-product-to-elements-of-a-list-of-lists — blhsing, Oct 09 '19 at 03:04

score 1 · Accepted Answer · answered Oct 09 '19 at 03:06

After some coding I have come up with a recursive solution. You can either use itertools.product or the functions below.

def rec_permutations(possibilities):
    counter = 0
    permutations_list=[]
    lst=[]
    return rec_permutations_helper(possibilities, permutations_list, counter, lst)

def rec_permutations_helper(possibilities, permutations_list, counter, lst):
    # Base case
    if counter == len(possibilities):
        permutations_list.append(lst)
        return
    # Recursive case
    else:
        locations = possibilities[counter]
        for location in locations:
            new_lst = lst + [location]      
            rec_permutations_helper(possibilities, permutations_list, counter+1, new_lst)

    return permutations_list

How to recursively create a list of permutations in python?

1 Answers1