Enumeration of all possible two-member group constellations

Question

I am looking for a way to enumerate all possible two-member group constellations for n members.

E.g., for n = 4 members the following 3 unique group constellations are possible (please note that neither the order of the members within a group nor the group order is of importance):

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

E.g., for n = 6 members the 15 unique constellations are possible:

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

For n members the number of unique groups can be calculated as

choose(n,2)*choose(n-2,2)*...*choose(2,2)/factorial(n/2),

where choose(n,k) is the binomial coef.

For n = 4 we have

choose(4,2)/factorial(4/2) = 3 

possible two-member group constellations. For n = 6 it is

choose(6,2)*choose(4,2)/factorial(6/2) = 15. 

An enumaration of the groups by hand is not feasible for more than n = 6 members. Is there an easy way to get a list/dataframe with all possible group constellations?

Answer 1

This looks like it works:

from itertools import combinations, islice

def cons(nums):
    if len(nums)%2 or len(nums)<2:
        raise ValueError
    if len(nums) == 2:
        yield (nums,)
        return
    for c in islice(combinations(nums, 2), len(nums)-1):
        for sub in cons(tuple(set(nums) - set(c))):
            yield ((c,) + sub)

def constellations(n):
    return cons(range(1, n+1))

for c in constellations(6):
    print c

Output:

((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))

Produces 105 entries for constellations(8) which checks out according to the formula.
Essentially, what I'm doing is grabbing just the combinations of the first element with each other element, and then passing the remainder into the recursion -- this ensures no repeated groups.

Answer 2

The R package partitions was written to answer questions like yours, which (in mathematical terms) is about enumerating all possible partitions of a set of six elements into three equivalence classes of two elements each.

The package provides two functions -- setparts() and listParts() -- that will enumerate all of the partitions. The functions differ solely in the format in which they return those results.

Here, I show the output of the listParts() function, mainly because the printed format that it returns is closer to what you included in the original question:

    library(partitions)
    P <- listParts(c(2,2,2)) 
    N <- sapply(P, print)
    # [1] (1,6)(2,5)(3,4)
    # [1] (1,6)(2,4)(3,5)
    # [1] (1,6)(2,3)(4,5)
    # [1] (1,2)(3,6)(4,5)
    # [1] (1,2)(3,5)(4,6)
    # [1] (1,2)(3,4)(5,6)
    # [1] (1,3)(2,6)(4,5)
    # [1] (1,3)(2,4)(5,6)
    # [1] (1,3)(2,5)(4,6)
    # [1] (1,4)(2,6)(3,5)
    # [1] (1,4)(2,5)(3,6)
    # [1] (1,4)(2,3)(5,6)
    # [1] (1,5)(2,6)(3,4)
    # [1] (1,5)(2,4)(3,6)
    # [1] (1,5)(2,3)(4,6)