Split a list into all pairs in all possible ways

Question

I am aware of many posts with the similar questions and have been through all of them. However, I am not able to do what I need.

I have list say l1=[0,1,2,3,4] which I want to partition into pair of tuples like following:

 [(0, 1), (2, 3), 4],
 [(0, 1), (2, 4), 3],
 [(0, 1), (3, 4), 2],
 [(0, 2), (1, 3), 4],
 [(0, 2), (1, 4), 5],
 [(0, 2), (3, 4), 1],
 [(0, 3), (1, 2), 4],
 [(0, 3), (2, 4), 1],
 [(0, 3), (1, 4), 2],
 [(0, 4), (1, 2), 3],
 [(0, 4), (1, 3), 2],
 [(0, 4), (2, 3), 1]

I tried a solution from the post how-to-split-a-list-into-pairs-in-all-possible-ways.

def all_pairs(lst):
    if len(lst) < 2:
        yield lst
        return
    a = lst[0]
    for i in range(1,len(lst)):
        pair = (a,lst[i])
        for rest in all_pairs(lst[1:i]+lst[i+1:]):
            yield [pair] + rest

I get the following output:

[(0, 1), (2, 3), 4]
[(0, 1), (2, 4), 3]
[(0, 2), (1, 3), 4]
[(0, 2), (1, 4), 3]
[(0, 3), (1, 2), 4]
[(0, 3), (1, 4), 2]
[(0, 4), (1, 2), 3]
[(0, 4), (1, 3), 2]

I find that there are some combinations which are missing from the list which I want.

I would appreciate any suggestion?

May I ask what is the use case for such a niche programming problem? — cs95, Aug 16 '17 at 03:58
Is your first list *complete* as to what you expect? Is the order within the pair irrelevant, and the order of the pairs as well? Both answers currently yield much longer answers. — Nick T, Aug 16 '17 at 04:05
Actually, why does 0 never appear last? Should you also have `[(1, 2), (3, 4), 0]`, `[(1, 3), (2, 4), 0]`, and others? — Nick T, Aug 16 '17 at 04:17
Yes, @NickT is right. I should also have other combinations which he mentioned. — Pankaj, Aug 16 '17 at 04:21
Is your input always going to have 5 values? If you expect to take variable lengths, sometimes odd, sometimes even, it might be easier if you allowed the odd one to show up as something like `(4, None)` or `(4,)` instead of a bare `4`. — Nick T, Aug 16 '17 at 04:24
I agree @NickT . For even number of elements, the solution in the my question works quite well. But in my problem, I have odd number of elements in the list. What you suggested is interesting? Let me try. — Pankaj, Aug 16 '17 at 04:27

cs95 · Accepted Answer · 2017-08-16T04:30:11.030

3

You can use itertools.permutations and filter out duplicates using frozenset:

In [173]: d = {frozenset([frozenset(x[:2]), frozenset(x[2:4]), x[-1]]) for x in itertools.permutations(l1, 
     ...: len(l1))}

In [174]: d2 = [sorted(x,  key=lambda x: (not isinstance(x, frozenset), x)) for x in d]

In [175]: sorted([[tuple(x[0]), tuple(x[1]), x[-1]] for x in d2])
Out[175]: 
[[(0, 4), (2, 3), 1],
 [(1, 2), (0, 3), 4],
 [(1, 2), (0, 4), 3],
 [(1, 2), (3, 4), 0],
 [(1, 3), (0, 2), 4],
 [(1, 3), (0, 4), 2],
 [(1, 3), (2, 4), 0],
 [(1, 4), (0, 2), 3],
 [(1, 4), (0, 3), 2],
 [(2, 3), (0, 1), 4],
 [(2, 3), (1, 4), 0],
 [(2, 4), (0, 1), 3],
 [(2, 4), (0, 3), 1],
 [(3, 4), (0, 1), 2],
 [(3, 4), (0, 2), 1]]

edited Aug 16 '17 at 04:30

answered Aug 16 '17 at 04:00

cs95

379,657
97
704
746

It looks like based on his expected list that he wants to ignore order, so `[(0, 1), (2, 3), 4] == [(0, 1), (3, 2), 4] == [(2, 3), (0, 1), 4]` – Nick T Aug 16 '17 at 04:08
@NickT Based on OP's desired output, it is not exhaustive? I'll look for some clarification from OP. – cs95 Aug 16 '17 at 04:10
What would be missing from his list if order inside and between pairs was ignored? – Nick T Aug 16 '17 at 04:12
@cᴏʟᴅsᴘᴇᴇᴅ `[(0, 1), (2, 3), 4]` is duplicate of `[(0, 1), (3, 2), 4]`. Actually, ordering inside a tuple is irrelevant. How do I get rid of these duplicates? – Pankaj Aug 16 '17 at 04:15
@NickT I used a frozenset and got rid of those duplicates. – cs95 Aug 16 '17 at 04:18
@Pankaj Please confirm that this is what you want. The other answer will not give you combinations other than `[(0, ...), ...]` – cs95 Aug 16 '17 at 04:20
Thanks @cᴏʟᴅsᴘᴇᴇᴅ. Still `[(1, 2), (0, 3), 4]` is duplicate of `[(0, 3), (1, 2), 4]` and some others. – Pankaj Aug 16 '17 at 04:23
Learned `itertools.permutations` from your answer. – stamaimer Aug 16 '17 at 04:42

score 1 · Answer 2 · answered Aug 16 '17 at 04:00

You could use itertools.permutations and then use a list comprehension to create pairs out of the first 4 items in each permuation:

l1=[0,1,2,3,4]
from itertools import permutations
l2 = permutations(l1)
l3 = [[(x[0], x[1]), (x[2], x[3]), x[4]] for x in l2]

score 1 · Answer 3 · answered Aug 16 '17 at 04:14

[[(0, i), tuple(item for item in l if item not in {0, i ,j}), j] for i in range(1, 5) for j in [item for item in l if item not in {0, i}]]

[[(0, 1), (3, 4), 2],
 [(0, 1), (2, 4), 3],
 [(0, 1), (2, 3), 4],
 [(0, 2), (3, 4), 1],
 [(0, 2), (1, 4), 3],
 [(0, 2), (1, 3), 4],
 [(0, 3), (2, 4), 1],
 [(0, 3), (1, 4), 2],
 [(0, 3), (1, 2), 4],
 [(0, 4), (2, 3), 1],
 [(0, 4), (1, 3), 2],
 [(0, 4), (1, 2), 3]]

Split a list into all pairs in all possible ways

3 Answers3

Linked