Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python: Generating All Possible Combinations?

  1. Feb 4, 2012 #1
    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. jcsd
  3. Feb 4, 2012 #2

    jhae2.718

    User Avatar
    Gold Member

  4. Feb 8, 2012 #3
    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
     
  5. Feb 21, 2012 #4
    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)
     
     
  6. Feb 21, 2012 #5

    jhae2.718

    User Avatar
    Gold Member

    You should be able to generate the combinations with the itertools.combination() function.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Python: Generating All Possible Combinations?
  1. Chess with Python (Replies: 2)

  2. Is Python the future? (Replies: 10)

  3. Python installation (Replies: 10)

Loading...