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