CODEWITHSUNDEEP
pythongraphcombinationscombinatorics
jbuddy_13
jbuddy_13

Reputation: 1286

Python: Extract all possible mutually exclusive pairs?

I have an assignment problem where I have N participants and need to find all possible 2-person assignments where every participant is assigned to exactly one pair.

When I use list(combinations(range(100), 2)) I get a "flat" list of about 4000 items, each a pair in the form of (i,j).

This is not what I'm looking for; there needs to be three levels of this array: [ [(1,2), (3,4),...], [(1,3), (2,4),...], ... ]

What's the best way to accomplish this effect in Python?

Upvotes: 0

Views: 74

Answers (2)

jbuddy_13
jbuddy_13

Reputation: 1286

def find_assignments(N):
    assignments = []
    size = N//2 
    elems = list(range(N))
    C = list(combinations(elems, size))
    for c in C:
        A = set(c)
        B = list(set(elems).difference(A))
        P = list(permutations(B))
        for p in P:
            edges = [(c[i], p[i]) for i in range(size)]
            assignments.append(edges)
        
    return assignments

Upvotes: 0

Alain T.
Alain T.

Reputation: 42133

You could write a recursive generator function:

def parings(L):
    if len(L)<=2:           # only 2 elements, single pair
        yield [tuple(L)]
        return
    for j in range(1,len(L)):                # first element paired with every other
        for rest in parings(L[1:j]+L[j+1:]): # with all pairings of remaining elements
            yield [(L[0],L[j])] + rest


for p in parings([1,2,3,4,5,6]): print(p)
                   
[(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)]

With N=10 you still get a reasonable number of patterns:

L = list(range(10))
print(sum(1 for _ in parings(L))) # 945

but it gets unmanageable real quick:

L = list(range(18))
print(sum(1 for _ in parings(L))) # 34,459,425

To decide on the size of your toy problem, you could adapt the recursive function to compute the number of results like this:

def pairingCount(N):
    if N<=2: return 1
    return (N-1) * pairingCount(N-2)

print(pairingCount(18)) # 34,459,425

Mathematically, the count can be expressed using factorials:

                n!
count =  ----------------
         (n/2)! * 2^(n/2)

Upvotes: 1

Related Questions