CODEWITHSUNDEEP
pythonpython-2.7
insomnia
insomnia

Reputation: 301

How to split a list in all possible?

For a list like

a = [1,2,3,4,5]

I want get all it's two elements subset in a result like:

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

I have written a silly code like:

b=[]

for i in combinations(a,2):
     for j in combinations(a,2):
         if(set(i).intersection(j)==set()):
             b.append((i,j))

Does anyone has a nice way?

Upvotes: 1

Views: 135

Answers (2)

Raymond Hettinger
Raymond Hettinger

Reputation: 226366

To make this algorithmically nicer, craft a recursive function that systematically reduces the problem rather than looking for intersections.

The recursive reduction step is basically "take k-elements out of the pool and then split over the remainder of the pool". Something like this:

from itertools import combinations
from pprint import pprint

def split(s, k=2):       # type:  (s: set) -> Iterable[List[tuple]]
    if len(s) <= k:
        yield []
    for thispair in combinations(s, k):
        remainder = s.difference(thispair)
        for otherpairs in split(remainder, k):
            yield [thispair] + otherpairs

pprint(list(split({1, 2, 3, 4, 5})))

There will need to be some additional logic to make sure that duplicate search paths aren't explored so that [{1, 2}, {3, 4}] and [{3, 4}, {1, 2}] aren't both in the output. This should be enough to get you started though.

Upvotes: 0

anati
anati

Reputation: 274

@insomnia The below piece of code is for generate permutation, I think it could be easy to customize it to fit your case:

import itertools
a = [1,2,3,4,5]
result = []
for combo in itertools.permutations(a, 2):
    result.append(combo)
print(len(result))

Upvotes: 1

Related Questions