Python: Generating All Possible Combinations?

[tangodirt]

Need a little help here, if anyone can offer any advice. The problem I have is this. I have a dictionary that contains keys, and their possible values. I need to generate every possible combination of key values where each key can take on one of the possible values.

For example, the dictionary might look something like:

Value Dictionary: {1: [[A], [B], [C]], 2: [[D], [E], [F], [G], [H]], 3: [[I], [J]], 4: [[K], [L], [M], [N]], 5: [[O], [P], [Q]]}

So, for the "1" key, the possible values it can assume are A, B, and C. For the "2" key, the possible values it can assume are D, E, F, G, and H. This continues for all keys, of undefined number of possible values. For this example, the number of possible combinations is something of the form: 3*5*2*4*3 = 360.

I need a way to output a 2D list containing every possible combination. So, the algorithm would output something like:

Combination List: [[A,D,I,K,O], [A,D,I,K,P], [A,D,I,K,Q], [A,D,I,L,O],...,[C,H,J,N,Q]]

Where the length of the combination list would be 360 and the width would be 5.

Does python have any built in way to do this, or will I have to come up with some logic to do this by hand? If I have to do it by hand, does anyone have any recommendations? I'm guessing recursion might be the best way to do this, but I'm not sure.

 

[jhae2.718]

Look at the itertools module.

 

[Obis]

Yes, it can be done with recursion, more particularly, using the technique of backtracking. I suggest you to learn it, it's a simple, yet powerful technique.

http://en.wikipedia.org/wiki/Backtracking

 

[phillip1882]

here was my valiant effort at it.

def patterns(dictionary):
   key = sorted(dictionary.keys())
   index = [0]*len(key)
   elements = {}
   next = 0
   while True:
      i = 0
      for value in key:
         if i == 0:
            elements[next] = dictionary[value][index[i]]
         else:
            elements[next] =elements[next][:] +dictionary[value][index[i]] 
         i += 1
      i = 0
      index[i] += 1
      while index[i] >= len(dictionary[key[i]]):
         index[i] = 0
         i += 1
         if i >= len(index):
            break
         else:
            index[i] += 1
      if i >= len(index):
         break
      next += 1
   return elements
val = {1: [["A"], ["B"], ["C"]], 2: [["D"], ["E"], ["F"], ["G"], ["H"]], 3: [["I"], ["J"]], 4: [["K"], ["L"], ["M"], ["N"]], 5: [["O"], ["P"], ["Q"]]}
print patterns(val)

 

[jhae2.718]

You should be able to generate the combinations with the itertools.combination() function.