title: How to merge two elements of two lists in python at random and ensure resulting entries are all unique?
body: <p>I have two lists, A and B, with an equal number of elements, although the elements in each list are not necessarily distinct.</p>
  
  <p>I would like to form a new list by coupling the elements from A and B at random (the random pairing is important).</p>
  
  <p>However, I also need to make sure that each pair in the resulting list is unique.  </p>
  
  <p>So far, I've been approaching the problem as follows, which works for small lists, but clearly is not suited to larger lists with many combinations.</p>
  
  <pre><code>from random import shuffle
  
  # Create a list of actors and events for testing
  events = ['P1','P1','P1','P2','P2','P2','P3','P3','P3','P4','P5','P6','P7','P7']
  actors = ['IE','IE','ID','ID','IA','IA','IA','IC','IB','IF','IG','IH','IH','IA']
  
  # Randomize the elements of each list
  shuffle(events)
  shuffle(actors)
  
  # Merge the two lists into a new list of pairs
  edgelist = zip(events,actors)
  
  # If the new list of pairs has all unique elements, then it is a good solution, otherwise try again at random
  x = set(edgelist)
  
  if len(edgelist) == len(x):
    break
  else:
    while True:
      shuffle(events)
      shuffle(actors)
      edgelist = zip(events,actors)
      x = set(edgelist)
      if len(edgelist) == len(x):
        break
  
  # Display the solution
  print 'Solution obtained: '
  for item in edgelist:
    print item
  </code></pre>
  
  <p>Can anyone suggest a modification or alternative approach that would scale to larger input lists?</p>
  
  <p>Thanks for the helpful replies.</p>
  
  <p><strong>Update</strong></p>
  
  <p>Turns out this is a more challenging problem than originally thought.  I think I now have a solution.  It may not scale incredibly well but works fine for small or medium sized lists.  It checks to see whether a solution is possible before starting, so assumptions about the distribution of the input lists aren't necessary.  I also included a few lines of code to show that the frequency distributions of the resulting list match the original.</p>
  
  <pre><code># Randomize the elements
  shuffle(events)
  
  # Make sure a solution is possible
  combinations = len(set(events))*len(set(actors))
  assert combinations &gt;= len(events) and combinations &gt;= len(actors) and len(events) == len(actors), 'No soluton possible!'
  
  # Merge the two lists into a new list of pairs (this will contain duplicates)
  edgelist = zip(events,actors)
  
  # Search for duplicates
  counts = collections.Counter(edgelist)
  duplicates = [i for i in counts if counts[i] &gt; 1]
  duplicate_count = len(duplicates)
  
  while duplicate_count &gt; 0:
  
    # Get a single duplicate to address
    duplicate = duplicates[0]
  
    # Find the position of the duplicate in the in edgelist
    duplicate_pos = edgelist.index(duplicate)
  
    # Search for a replacement
    swap = choice(edgelist)
    swap_pos = edgelist.index(swap)
  
    if (swap[0],duplicate[1]) not in edgelist: 
      edgelist[duplicate_pos] = (swap[0],duplicate[1])
      edgelist[swap_pos] = (duplicate[0],swap[1])
  
    # Update duplicate count
    counts = collections.Counter(edgelist)
    duplicates = [i for i in counts if counts[i] &gt; 1]
    duplicate_count = len(duplicates)
  
  
  # Verify resulting edgelist and frequency distributions
  
  print 'Event Frequencies: '
  print sorted([y for (x,y) in list(collections.Counter(events).items())], reverse=True)
  
  print 'Edgelist Event Frequencies: '        
  print sorted([y for (x,y) in list(collections.Counter([x for (x,y) in edgelist]).items())], reverse=True)
  
  print 'Actor Frequencies: '        
  print sorted([y for (x,y) in list(collections.Counter(actors).items())], reverse=True)
  
  print 'Edgelist Actor Frequencies: '        
  print sorted([y for (x,y) in list(collections.Counter([y for (x,y) in edgelist]).items())], reverse=True)
  
  assert len(set(edgelist)) == len(events) == len(actors)
  </code></pre>