title: Python: How to generate all combinations of lists of tuples without repeating contents of the tuple
body: <p>I'm working with a bit of a riddle:</p>
  
  <p>Given a dictionary with tuples for keys: <code>dictionary = {(p,q):n}</code>, I need to generate a list of new dictionaries of every combination such that neither p nor q repeat within the new dictionary. And during the generation of this list of dictionaries, or after, pick one of the dictionaries as the desired one based on a calculation using the dictionary values.</p>
  
  <p>example of what I mean (but much smaller):</p>
  
  <p><code>dictionary = {(1,1): 1.0, (1,2): 2.0, (1,3): 2.5, (1,4): 5.0, (2,1): 3.5, (2,2): 6.0, (2,3): 4.0, (2,4): 1.0}</code></p>
  
  <p>becomes</p>
  
  <p><code>listofdictionaries = [{(1,1): 1.0, (2,2): 6.0}, {(1,1): 1.0, (2,3): 4.0}, (1,1): 1.0, (2,4): 1.0}, {(1,2): 2.0, (2,1): 3.5}, {(1,2): 2.0,  (2,3): 4.0},</code> etc.</p>
  
  <p>a dictionary like: <code>{(1,1): 1.0, (2,1): 3.5}</code> is not allowable because q repeats.</p>
  
  <p>Now my sob story: I'm brand new to coding... but I've been trying to write this script to analyze some of my data. But I also think it's an interesting algorithm riddle. I wrote something that works with very small dictionaries but when I input a large one, it takes way too long to run (copied below). In my script attempt, I actually generated a list of combinations of tuples instead that I use to refer to my master dictionary later on in the script. I'll copy it below:</p>
  
  <p><em>The dictionary tuple keys were generated using two lists: "ExpList1" and "ExpList2"</em></p>
  
  <pre><code>#first, I generate all the tuple combinations from my ExpDict dictionary
  combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))
  
  #then I generate a list of only the combinations that don't repeat p or q
  uniquecombolist = []
  for foo in combos:
      counter = 0
      listofp = []
      listofq = []
      for bar in foo:
          if bar[0] in listofp or bar[1] in listofq:
              counter=+1
              break
          else:
              listofp.append(bar[0])
              listofq.append(bar[1])
      if counter == 0:
          uniquecombolist.append(foo)
  </code></pre>
  
  <p>After generating this list, I apply a function to all of the dictionary combinations (iterating through the tuple lists and calling their respective values from the master dictionary) and pick the combination with the smallest resulting value from that function. </p>
  
  <p>I also tried to apply the function while iterating through the combinations picking the unique p,q ones and then checking whether the resulting value is smaller than the previous and keeping it if it is (this is instead of generating that list "uniquecombolist", I end up generating just the final tuple list) - still takes too long.</p>
  
  <p>I think the solution lies in embedding the p,q-no-repeat and the final selecting function DURING the generation of combinations. I'm just having trouble wrapping my head around how to actually do this.</p>
  
  <p>Thanks for reading!
  Sara</p>
  
  <p>EDIT: </p>
  
  <p>To clarify, I wrote an alternative to my code that incorporates the final function (basically root mean squares) to the sets of pairs. </p>
  
  <pre><code>`combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))
  
  
  prevRMSD = float('inf')
  for foo in combos:
      counter = 0
      distanceSUM = 0
      listofp = []
      listofq = []
      for bar in foo:
          if bar[0] in listofp or bar[1] in listofq:
              counter=+1
              break
          else:
              listofp.append(bar[0])
             listofq.append(bar[1])
          distanceSUM = distanceSUM + RMSDdict[bar]
      RMSD = math.sqrt (distanceSUM**2/len(foo))
      if counter == 0 and RMSD&lt; prevRMSD:
          chosencombo = foo
          prevRMSD = RMSD`
  </code></pre>
  
  <p>So if I could incorporate the RMS calculation during the set generation and only keep the smallest one, I think that will solve my combinatorial problem.</p>