Python: Find specific and distinct set of combinations

Question

I have 4 departments:

# department 1, 2, 3, 4
departments = ['d1','d2','d3','d4']

Each department has 8 units:

d1 = [1,2,3,4,5,6,7,8]
d2 = [1,2,3,4,5,6,7,8]
d3 = [1,2,3,4,5,6,7,8]
d4 = [1,2,3,4,5,6,7,8]

I need to create working groups.

A working group is comprised of 2 units from each department, where there is only one individual from any given numbered unit. 8 total units, 2 per department, must contain 1 - 8 with no duplicate unit numbers.

# Example Valid:
working_group_1 = ['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48']
working_gorup_2 = ['d18', 'd17', 'd26', 'd25', 'd34', 'd33', 'd42', 'd41']
working_gorup_3 = ['d14', 'd18', 'd22', 'd26', 'd31', 'd35', 'd43', 'd47']
# each working group has 8 total individuals
# each working group has 2 individuals from each group
# each working group has 1 individual from each section 1-8

# Example Invalid:
working_group_4 = ['d12', 'd11', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48']

# wg_4 is invalid because it is a copy of wg_1, where individuals from section 1, 2 are both assigned from the same department, just in a different order.

# This is not what I looking for, but might be close-ish
# The following snippet will give me all permutations
# e.g., ('d11', 'd12', 'd24', 'd27', 'd32', 'd34', 'd41', 'd46')
# The problem with this example is that, there are two individuals from unit 1
# - d11, d41 <- this is not allowed

import itertools

# Make the groups
groups = [[f'd{i+1}{j+1}' for j in range(8)] for i in range(4)]
lists = [list(itertools.combinations(groups[i],2)) for i in range(len(groups))]

#Generate list of all combinations, selecting 2 units from each department
all_combinations = [] 
for i in itertools.product(lists[0],lists[1],lists[2],lists[3]):
    all_combinations.append(i[0]+i[1]+i[2]+i[3])

#Output all combinations
print(all_combinations)

Any help is appreciated, thanks in advance.

Answer 1

You were close with your approach. This seems a typical backtracking problem, where for every taken set of units, you have to reduce the unit-pool. Here is a recursive generator function:

def backtrack_groups(deps, units_per=2, used_units=None):
    if not deps:  # base case: no mo' departments
        yield []
        return
    used_units = used_units or set()
    poolsize = len(used_units) + units_per * len(deps)
    pool = [u for u in range(1, poolsize+1) if u not in used_units]
    # choose all possible unit combinations for the first (remaining) department ...
    dep, *rest = deps
    for units in combinations(pool, units_per):
        used_units.update(units)
        for group in backtrack_groups(rest, units_per, used_units):
            # ... and combine it with every possible group from
            # the remaining departments (honoring the used_units constraint)
            yield [f"{dep}{u}" for u in units] + group
        # as you have exhausted these two units for the current department
        # you put them back in the pool
        used_units.difference_update(units)

>>> groups = backtrack_groups(departments)
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48']
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd35', 'd37', 'd46', 'd48']
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd35', 'd38', 'd46', 'd47']
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd36', 'd37', 'd45', 'd48']
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd36', 'd38', 'd45', 'd47']
>>> next(groups)
['d11', 'd12', 'd23', 'd24', 'd37', 'd38', 'd45', 'd46']
# ...

And, general case:

>>> list(backtrack_groups(["d1", "d2"], 1))
[['d11', 'd22'], 
 ['d12', 'd21']]
>>> list(backtrack_groups(["d1", "d2"], 2))
[['d11', 'd12', 'd23', 'd24'], 
 ['d11', 'd13', 'd22', 'd24'], 
 ['d11', 'd14', 'd22', 'd23'], 
 ['d12', 'd13', 'd21', 'd24'], 
 ['d12', 'd14', 'd21', 'd23'], 
 ['d13', 'd14', 'd21', 'd22']]

len(list(groups)) (with a new generator) is 2520 which is exactly nCr(8, 2) * nCr(6, 2) * nCr(4, 2) * nCr(2, 2) with nCr being n-choose-r or "n over r". So the combinatoric numbers work out ;-)

Answer 2

Slightly shorter recursive approach:

from itertools import product as pr
def combos(d, c = []):
   if not d:
      yield c
   else:
      s = set()
      for i in pr(*[enumerate(j) for j in d[0][-1]]):
         if (k:=tuple(sorted((l:=list(zip(*i)))[1]))) not in s and len(set(l[0])) == len(l[0]):
            yield from combos([[a, [[y for x, y in enumerate(h) if x not in l[0]] for h in b]] for a, b in d[1:]], c+[d[0][0]+str(y) for y in l[1]])
            s.add(k)

departments, units = ['d1','d2','d3','d4'], 8
result = list(combos([[i, [[*range(1, units+1)]]*(units//len(departments))] for i in departments]))
print(len(result))

Output:

2520

It is important to note that the solution above will produce combinations where units repeat across results, i.e:

[['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48'], 
 ['d11', 'd12', 'd23', 'd24', 'd35', 'd37', 'd46', 'd48']]

If every unit has to be unique, then a slight update can be made to combos:

def combos(d, c = []):
   if not d:
      yield c
   else:
      s = set()
      for i in pr(*[enumerate(j) for j in d[0][-1]]):
         if (k:=tuple(sorted((l:=list(zip(*i)))[1]))) not in s and len(set(l[0])) == len(l[0]):
            yield next(combos([[a, [[y for x, y in enumerate(h) if x not in l[0]] for h in b]] for a, b in d[1:]], c+[d[0][0]+str(y) for y in l[1]]))
            s.add(k)

Output:

[['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48'], ['d11', 'd13', 'd22', 'd24', 'd35', 'd36', 'd47', 'd48'], ['d11', 'd14', 'd22', 'd23', 'd35', 'd36', 'd47', 'd48'], ['d11', 'd15', 'd22', 'd23', 'd34', 'd36', 'd47', 'd48'], ['d11', 'd16', 'd22', 'd23', 'd34', 'd35', 'd47', 'd48'], ['d11', 'd17', 'd22', 'd23', 'd34', 'd35', 'd46', 'd48'], ['d11', 'd18', 'd22', 'd23', 'd34', 'd35', 'd46', 'd47'], ['d12', 'd13', 'd21', 'd24', 'd35', 'd36', 'd47', 'd48'], ['d12', 'd14', 'd21', 'd23', 'd35', 'd36', 'd47', 'd48'], ['d12', 'd15', 'd21', 'd23', 'd34', 'd36', 'd47', 'd48'], ['d12', 'd16', 'd21', 'd23', 'd34', 'd35', 'd47', 'd48'], ['d12', 'd17', 'd21', 'd23', 'd34', 'd35', 'd46', 'd48'], ['d12', 'd18', 'd21', 'd23', 'd34', 'd35', 'd46', 'd47'], ['d13', 'd14', 'd21', 'd22', 'd35', 'd36', 'd47', 'd48'], ['d13', 'd15', 'd21', 'd22', 'd34', 'd36', 'd47', 'd48'], ['d13', 'd16', 'd21', 'd22', 'd34', 'd35', 'd47', 'd48'], ['d13', 'd17', 'd21', 'd22', 'd34', 'd35', 'd46', 'd48'], ['d13', 'd18', 'd21', 'd22', 'd34', 'd35', 'd46', 'd47'], ['d14', 'd15', 'd21', 'd22', 'd33', 'd36', 'd47', 'd48'], ['d14', 'd16', 'd21', 'd22', 'd33', 'd35', 'd47', 'd48'], ['d14', 'd17', 'd21', 'd22', 'd33', 'd35', 'd46', 'd48'], ['d14', 'd18', 'd21', 'd22', 'd33', 'd35', 'd46', 'd47'], ['d15', 'd16', 'd21', 'd22', 'd33', 'd34', 'd47', 'd48'], ['d15', 'd17', 'd21', 'd22', 'd33', 'd34', 'd46', 'd48'], ['d15', 'd18', 'd21', 'd22', 'd33', 'd34', 'd46', 'd47'], ['d16', 'd17', 'd21', 'd22', 'd33', 'd34', 'd45', 'd48'], ['d16', 'd18', 'd21', 'd22', 'd33', 'd34', 'd45', 'd47'], ['d17', 'd18', 'd21', 'd22', 'd33', 'd34', 'd45', 'd46']]

Now, every department unit is unique.