1

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]}
Axe319
  • 4,255
  • 3
  • 15
  • 31
Shreya Joshi
  • 31
  • 2
  • there's `itertools` which provide this functionality. – Mahrkeenerh Oct 13 '21 at 10:08
  • @Stef I don't think the most voted answer of the question is going to help – Dani Mesejo Oct 13 '21 at 10:16
  • 1
    @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. – Axe319 Oct 13 '21 at 10:19
  • A similar but not identical question: [Get n * k unique sets of 2 from list of length n in Python](https://stackoverflow.com/questions/64604793/get-n-k-unique-sets-of-2-from-list-of-length-n-in-python/64606498#64606498) – Stef Oct 13 '21 at 10:27

1 Answers1

0

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')]]
Stef
  • 13,242
  • 2
  • 17
  • 28
  • 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] – Shreya Joshi Oct 16 '21 at 10:59
  • @ShreyaJoshi Not sure what you mean. Can you provide an example of the output with input list [1, 2, 3, 4]? – Stef Oct 16 '21 at 11:01
  • Just edited the comment and added the example – Shreya Joshi Oct 16 '21 at 11:04
  • @ShreyaJoshi Then you can use either [`map`](https://docs.python.org/3/library/functions.html#map) or a [list comprehension](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions) 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')]` – Stef Oct 16 '21 at 11:11
  • For some reason, this gives maximum recursion depth exceeded error.. – Shreya Joshi Oct 16 '21 at 11:27
  • @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. – Stef Oct 16 '21 at 11:33
  • 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."* – Stef Oct 16 '21 at 11:34
  • 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. – Shreya Joshi Oct 16 '21 at 11:39
  • 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. – Stef Oct 16 '21 at 11:40
  • 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. – Stef Oct 16 '21 at 11:43
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/238217/discussion-between-shreya-joshi-and-stef). – Shreya Joshi Oct 16 '21 at 11:45