CODEWITHSUNDEEP
python
FrederikNS
FrederikNS

Reputation: 5772

Partitioning a sequence into sets of unique pairs

I'm in need a of function which can split a sequence into pairs, and then combine them such that all elements in a combination is unique. I have tried a number of approaches using python's itertools, but have not found a solution.

To illustrate i would like a function which would take this sequence: [1, 2, 3, 4]

and split it into the following 3 combinations:

[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4], [2, 3]]

it should also work for longer sequences, but does not have to handle sequences of odd length. eg.

[1,2,3,4,5,6]

splits into the following 15 combinations:

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 6], [4, 5]]
[[1, 3], [2, 4], [5, 6]]
[[1, 3], [2, 5], [4, 6]]
[[1, 3], [2, 6], [4, 5]]
[[1, 4], [2, 3], [5, 6]]
[[1, 4], [2, 5], [3, 6]]
[[1, 4], [2, 6], [3, 5]]
[[1, 5], [2, 3], [4, 6]]
[[1, 5], [2, 4], [3, 6]]
[[1, 5], [2, 6], [3, 4]]
[[1, 6], [2, 3], [4, 5]]
[[1, 6], [2, 4], [3, 5]]
[[1, 6], [2, 5], [3, 4]]

... and so on.

The CAS called Maple has this function implemented under the name setpartition.

Edit: fixed a critical late night typing error pointed out by wks, and clarified the outputs.

Upvotes: 4

Views: 2011

Answers (3)

pillmuncher
pillmuncher

Reputation: 10162

itertoolsis indeed your friend:

from itertools import permutations

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

for each in permutations([1, 2, 3, 4, 5, 6]):
    print map(list, group(each))

Result:

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 4], [6, 5]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 5], [6, 4]]
[[1, 2], [3, 6], [4, 5]]
[[1, 2], [3, 6], [5, 4]]
[[1, 2], [4, 3], [5, 6]]
[[1, 2], [4, 3], [6, 5]]
[[1, 2], [4, 5], [3, 6]]
...

[EDIT] @FrederikNS: After you clarified your question and found an answer yourself, here is my solution:

from itertools import combinations

def setpartition(iterable, n=2):
    iterable = list(iterable)
    partitions = combinations(combinations(iterable, r=n), r=len(iterable) / n)
    for partition in partitions:
        seen = set()
        for group in partition:
            if seen.intersection(group):
                break
            seen.update(group)
        else:
            yield partition

for each in setpartition([1, 2, 3, 4]):
    print each
print
for each in setpartition([1, 2, 3, 4, 5, 6]):
    print each

Result:

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

((1, 2), (3, 4), (5, 6))
((1, 2), (3, 5), (4, 6))
((1, 2), (3, 6), (4, 5))
((1, 3), (2, 4), (5, 6))
((1, 3), (2, 5), (4, 6))
((1, 3), (2, 6), (4, 5))
((1, 4), (2, 3), (5, 6))
((1, 4), (2, 5), (3, 6))
((1, 4), (2, 6), (3, 5))
((1, 5), (2, 3), (4, 6))
((1, 5), (2, 4), (3, 6))
((1, 5), (2, 6), (3, 4))
((1, 6), (2, 3), (4, 5))
((1, 6), (2, 4), (3, 5))
((1, 6), (2, 5), (3, 4))

Upvotes: 5

FrederikNS
FrederikNS

Reputation: 5772

I finally got it my self (pillmuncher's answer really gave me a nudge in the right direction, and the group function is entirely his):

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

def set_partition(iterable, n=2):
    set_partitions = set()

    for permutation in itertools.permutations(iterable):
        grouped = group(list(permutation), n)
        sorted_group = tuple(sorted([tuple(sorted(partition)) for partition in grouped]))
        set_partitions.add(sorted_group)

    return set_partitions

partitions = set_partition([1,2,3,4], 2)
for part in partitions:
    print(part)

this prints :

((1, 4), (2, 3))
((1, 3), (2, 4))
((1, 2), (3, 4))

Upvotes: 1

Harrison
Harrison

Reputation: 830

Try this:

def function(list):
    combinations = []
    for i in list:
        for i2 in list:
            if not [i2, i] in combinations:
                 combinations.append([i, i2])
    return combinations

This returns every possible combination.

Hope this helps!

Upvotes: -1

Related Questions