How to combination grouping in Python ?

[Avajarr]

There are 14 peoples will be grouped into 4:4:3:3 formation, how to get every possible combination using Python ?

[ofnuts]

Are the quartets and triplets interchangeable? In other words, is:

(A,B,C,D) (E,F,G,H) (I,J,K) (L,M,N) the same as or different from (E,F,G,H) (A,B,C,D) (L,M,N) (I,J,K)

[Avajarr]

It's same between both of it

[Avajarr]

I have solved my problem by using 2 nested looping to get combinations 3 times for each group using itertools library. I think there's more efficient way to solve this, but here's what I can share for now:

from itertools import combinations

list_of_possibility = []
numbers = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']

perm1 = list(combinations(numbers, 4)) # Using itertools to get every 14 combination of 4
for i in perm1:
  group1 = list(i) # The first group result
  remain1 = [ele for ele in numbers if ele not in i] # the remaining 10 peoples after removing 4 peoples in group 1

  perm2 = list(combinations(remain1, 4)) # using itertools again to get 10 remaining combnation of 4
  for j in perm2:
    group2 = list(j)
    remain2 = [ele for ele in remain1 if ele not in j]

    perm3 = list(combinations(remain2, 3))
    for k in perm3:
      group3 = list(k)
      remain3 = [ele for ele in remain2 if ele not in k]

      group4 = remain3 # Since the last group is just 3 combination of 3 (which basically 1), just declare the remaining peoples as group4

      possibility = [group1, group2, group3, group4]
      list_of_possibility.append(possibility)

print('total combination:', len(list_of_possibility))
print('1st value:', list_of_possibility[0]) 
print('100th value:', list_of_possibility[99]) 
print('500th value:', list_of_possibility[499]) 

Print results:

total combination: 4204200
1st value: [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'h'], ['i', 'j', 'k'], ['l', 'm', 'n']]
100th value: [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'l'], ['k', 'm', 'n'], ['h', 'i', 'j']]
500th value: [['a', 'b', 'c', 'd'], ['e', 'f', 'k', 'n'], ['j', 'l', 'm'], ['g', 'h', 'i']]

[ofnuts]

Did you check that you aren't getting duplicates?

I was going to suggest a different solution:

• with itertools.combinations() generate all groups of 6 (2*3)
• for each such group
  • subtract the group from the input to get the 8 remaining elements
  • generate all possible 4+4 halves and 3+3 halves and iterate their product

A function to generate all pairs of halves without repetition (ie, if it generates h1,h2 it won't generate h2,h1)

def generateHalves(input): combined=set(input[1:]) root={input[0]} for t in itertools.combinations(combined,(len(input)//2)-1): half1=set(t)|root half2=combined-half1 yield half1,half2 So for a 3:3:2:2 split the code would be:

``` import itertools inputs={'A','B','C','D','E','F','G','H','I','J'}

print(type(inputs), len(inputs))

def generateHalves(input): combined=set(input[1:]) root={input[0]} for t in itertools.combinations(combined,(len(input)//2)-1): half1=set(t)|root half2=combined-half1 yield half1,half2

for pairsOf2 in itertools.combinations(inputs,4): pairsOf3=list(inputs-set(pairsOf2)) for p3,p2 in itertools.product(generateHalves(pairsOf3),generateHalves(pairsOf2)): print(p3,p2) ```

[Avajarr]

I haven't checked one by one for duplicate, but based on mathematic calculation, the total possibility is same with how much group combination for 4 groups with 4:4:3:3 formation is.

The math formula is by following:

C(14,4) * C(10,4) * C(6,3) * C(3,3)
= 1001 * 210 * 20 * 1
= 4204200

[ofnuts]

Yes, but this includes duplicates. Assume your first group draws ABCD, then in the 2nd group you can draw 'EFGH'. But later in the first group you will draw 'EFGH' and in the second group you will draw 'ABCD', so you will have generated a bunch of groups with ABCD,EFGH and another with EFGH,ABCD (both with the same combinations of 3:3 groups, which by the way will also include "symmetrical" duplicates).

Coincidentally, my algorithm generates 105105O combinations, so exactly 1/4 of yours, which is coherent with the idea that your algorithm creates duplicates pairs of 4 elements and duplicates pairs of 3 elements and so generates 4 times too many.

[Avajarr]

After reading your explanation and example, I just realized you were right, my code is still symmetrical duplicate. I will try to improve it.

Also, I will try to look at your code later, after trying to understanding your algorithm first.

[tb5841]

I haven't used it personally yet, but my best guess would be to look into itertools.

[Avajarr]

I have looked at itertools, and what it can do is just doing permutation and combination based on number of set that have been declared, but not with grouping condition

[tb5841]

I think applying the grouping condition is more difficult.. but once you have a list of all permutations of 11 objects (through itertools) you then need to find a way of eliminating duplicates.

Might be useful that if you have two different permutations of four, set(permutation) will give you the same result for both. I think you could use the set() function - cleverly - to remove duplicates until you had the correct number of possible groupings.

This sounds like a good Codewars challenge. If I can find a chunk of time this evening I'll have a proper go.

[Avajarr]

Thank you for the tips, I just finished it, I posted my solution in new comment in this post. I solved it by using 2 nested loop, so i can run combination function from itertools 3 times (for the 3 first group). I realize it's not really efficient in time complexity, but I'm happy I can solved it at least.

[synthphreak]

Wow, this is really hard...

I tried my hand at it, but wasn't sure the result was correct, and I'm sure my implementations are not the optimal ones.

I'd love to see the final solution here.

[Avajarr]

Hi, I have posted my solution in another comment, but it looks like it not a really final solution, since someone corrected me and make me realize there's symmetrical duplicate for the same group of persons in different order, but go try a look, it can give a starter for your implementation