CODEWITHSUNDEEP
pythonsetpartition
Pablo
Pablo

Reputation: 733

python - split a list in pairs and unique elements

I'm having a hard time trying to achieve the following: I have a list (say, [a,b,c,d]) and I need to partition it into pairs and unique elements in every possible way (order is not important), i.e.:

[a,b,c,d], [(a,b), c,d], [(a,b), (c,d)], [a, (b,c), d], [(a,d), (b, c)]...

and so on. This thread solves the problem when only pairs are used, but I need also the unique elements and I cannot get it to do it. Any idea will be much appreciated. Thanks!

Upvotes: 4

Views: 1687

Answers (4)

Leo Cavaille
Leo Cavaille

Reputation: 465

Maybe a simpler solution would be a recursive one. Just create every combination with the first element and move to sublists without it.

def partition(L):
    if len(L) <= 1:
        return [L]

    partitions = [[L[0]] + p for p in partition(L[1:])]
    for i in xrange(1, len(L)):
        partitions.extend([[(L[0], L[i])] + p for p in partition(L[1:i]+L[i+1:])])

    return partitions

Upvotes: 3

Martin E. Zulliger
Martin E. Zulliger

Reputation: 849

Ok! Let's see, this is not the prettiest I could come up with, and I'm pretty sure we could cut a few lines from it, but at least its generic (extracts tuples up to max size), and I wanted to share it with you guys!

from itertools import permutations

thelist = ['a', 'b', 'c', 'd']

def tuplets(l, max):
    out = []
    for i in permutations(l):
        for j in xrange(1, max + 1):
            pick(list(i), max, out, [], j, 0)
    return out

def pick(l, max, out, branch, num, idx):
    if (num == 1):
        picked = l[idx]
    else:
        picked = tuple(l[idx:idx+num])

    newBranch = list(branch)
    newBranch.append(picked)

    if idx + num == len(l):
        out.append(newBranch)
        return

    for i in xrange(1, max + 1):
        if idx + i + num > len(l):
            continue
        pick(l, max, out, newBranch, i, idx + num)

print tuplets(thelist, 2)

Upvotes: 0

JuniorCompressor
JuniorCompressor

Reputation: 20025

Given a function that given an even length list, splits it in pairs without taking order into account:

def gen_only_pairs(l):
    if not l:
        yield []
        return

    for i in xrange(1, len(l)):
        l[1], l[i] = l[i], l[1]
        for v in gen_only_pairs(l[2:]):
            yield [(l[0], l[1])] + v
        l[1], l[i] = l[i], l[1]

we can generate our wanted results:

from itertools import combinations

def gen(a):
    # For all number of pairs
    for npairs in xrange(0, len(a) // 2 + 1): 
        # For each combination of 2 * npairs elements
        for c in combinations(a, 2 * npairs):
            rest = list(set(a) - set(c))
            # Generate all splits of combination into pairs
            for v in gen_only_pairs(list(c)):
                # Also add the rest of the elements
                yield v + rest

and use like that:

for c in gen([1, 2, 3, 4]):
    print c

Output:

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

Upvotes: 1

Alexander
Alexander

Reputation: 109546

Use combinations from itertools:

from itertools import combinations

data = ['a', 'b', 'c', 'd']
pairs = [i for i in combinations(data, 2)]
>>> pairs
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

triplets = [i for i in combinations(data, 3)]
>>> triplets
[('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd')]

etc.

Upvotes: 0

Related Questions