# Python: Generating All Possible Combinations?

1. Feb 4, 2012

### 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:
Code (Text):
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:

Code (Text):
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.

Last edited: Feb 4, 2012
2. Feb 4, 2012

3. Feb 8, 2012

### 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

4. Feb 21, 2012

### phillip1882

here was my valiant effort at it.
Code (Text):

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)

5. Feb 21, 2012

### jhae2.718

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