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.

• blhsing: What you need is simply itertools.product for a cartesian product.
• azizbro: could you provide a more detailed response please?
• blhsing: 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.
• Klaus D.: "But I want to do this recursively." No, you don't want to do it recursively. You just don't know that yet.
• blhsing: @Azizbro Here's an example: stackoverflow.com/questions/3034014/…

Answer 1

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