Fastest way to get sets of all mutually exclusive pairs that can be formed from a list in python? [duplicate]

Question

Consider a list : [A,B,C,D]

I have to find the fastest way split the list in all possible sets of pairs such that the pairs are mutually exclusive: For example, for the given list, the result should be:

1. {[A,B],[C,D]}
2. {[A,C],[B,D]}
3. {[A,D],[B,C]}

Roque

there's itertools which provide this functionality. – Questionless

@Stef I don't think the most voted answer of the question is going to help – Vitus

@DaniMesejo The most voted answer doesn't even do a good job of helping the question its answering. However, the question itself and remaining answers seem relevant. – Sirup

A similar but not identical question: Get n * k unique sets of 2 from list of length n in Python – Butcherbird

Answer 1

Simple recursive version:

def all_pairings(l):
  if len(l) == 0:
    return [[]]
  else:
    return [[(l[0],l[i])] + p for i in range(1,len(l)) for p in all_pairings(l[1:i]+l[i+1:])]

all_pairings('')
# [[]]

all_pairings('ab')
# [[('a', 'b')]]

all_pairings('abcd')
# [[('a', 'b'), ('c', 'd')], [('a', 'c'), ('b', 'd')], [('a', 'd'), ('b', 'c')]]

all_pairings('abcdef')
# [[('a', 'b'), ('c', 'd'), ('e', 'f')], [('a', 'b'), ('c', 'e'), ('d', 'f')],
#  [('a', 'b'), ('c', 'f'), ('d', 'e')], [('a', 'c'), ('b', 'd'), ('e', 'f')],
#  [('a', 'c'), ('b', 'e'), ('d', 'f')], [('a', 'c'), ('b', 'f'), ('d', 'e')],
#  [('a', 'd'), ('b', 'c'), ('e', 'f')], [('a', 'd'), ('b', 'e'), ('c', 'f')],
#  [('a', 'd'), ('b', 'f'), ('c', 'e')], [('a', 'e'), ('b', 'c'), ('d', 'f')],
#  [('a', 'e'), ('b', 'd'), ('c', 'f')], [('a', 'e'), ('b', 'f'), ('c', 'd')],
#  [('a', 'f'), ('b', 'c'), ('d', 'e')], [('a', 'f'), ('b', 'd'), ('c', 'e')],
#  [('a', 'f'), ('b', 'e'), ('c', 'd')]]

Butcherbird

Thank you so much, that did just what I wanted! :) Just another extension to my question, what will the code look like if I were to sum up values associated with each pair? For eg., [a,b,c,d] would return [[('a', 'b'), ('c', 'd')], [('a', 'c'), ('b', 'd')], [('a', 'd'), ('b', 'c')]] .. If each pair had a score associated with it like ->(a,b): 10, (c,d):20, (a,c):30, (b,d):40, (a,d):50, (b,c):60.. then [[('a', 'b'), ('c', 'd')], [('a', 'c'), ('b', 'd')], [('a', 'd'), ('b', 'c')]] would look like [10+20,30+40,50+60]=[30,70,110] – Roque

@ShreyaJoshi Not sure what you mean. Can you provide an example of the output with input list [1, 2, 3, 4]? – Butcherbird

Just edited the comment and added the example – Roque

@ShreyaJoshi Then you can use either map or a list comprehension to iterate on the result of all_pairings. Assuming your values are in a dict called d={('a','b'): 10, ('c','d'):20, ('a','c'):30, ...}, then you can write result = [sum(d[pair] for pair in pairing) for pairing in all_pairings('abcd')] – Butcherbird

For some reason, this gives maximum recursion depth exceeded error.. – Roque

@ShreyaJoshi What? all_pairings is a recursive function, so it could give a recursion error if called on a list too long. But if all_pairing(lst) alone doesn't give a recursion error, then [sum(d[pair] for pair in pairing) for pairing in all_pairings(lst)] shouldn't give a recursion error either. – Butcherbird

Actually, even recursion error seems unlikely. Take this comment from the duplicate question: "By default Python has a return stack 1000 calls deep. You are recursing on pairs of digits, so this should not be an issue until your list is almost 2000 items long. At only 50 items you get more than 5*10^31 combinations; you will run into billion-year computations long before stack depth becomes an issue." – Butcherbird

def all_pairings(lst): if len(lst) == 0: return [[]] else: result = [(sum(len(pair)) for pair in pairing) for pairing in all_pairings(lst)] return result For test, I have replaced the dictionary with len function. Can you suggest where this is going wrong? Because this is throwing a Recursion error. – Roque

I strongly advise separating the logic. Write the function all_pairings exactly the way I wrote it in my answer, then iterate on the return of all_pairings the way I shown in my comment. Do not try to mix the two. – Butcherbird

If you really wanted to mix the two, then the else: should be return [d[(l[0],l[i])] + p for i in range(1,len(l)) for p in all_pairings(l[1:i]+l[i+1:])], where d is the dictionary. But again, I advise against it. – Butcherbird

Let us continue this discussion in chat. – Roque