Python：查找特定且不同的组合集
Python: Find specific and distinct set of combinations
我有 4 个部门：
# department 1, 2, 3, 4
departments = ['d1','d2','d3','d4']
每个部门有8个单位：
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]
我需要创建工作组。
一个工作组由每个部门的 2 个单位组成，其中任何给定编号的单位只有一个人。总共 8 个单位，每个部门 2 个，必须包含 1 - 8 且没有重复的单位编号。
# 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)
感谢任何帮助，提前致谢。
您的方法很接近。这似乎是一个典型的回溯问题，对于每组单元，您都必须减少单元池。这是一个递归生成器函数：
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']
# ...
并且，一般情况：
>>> 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))（使用新生成器）是 2520，正好是 nCr(8, 2) * nCr(6, 2) * nCr(4, 2) * nCr(2, 2)，nCr 是 n-choose-r 或“n over r”。所以组合数算出来了 ;-)
稍微短一点的递归方法：
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))
输出：
2520
重要的是要注意上面的解决方案将产生单元在结果中重复的组合，即：
[['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48'],
['d11', 'd12', 'd23', 'd24', 'd35', 'd37', 'd46', 'd48']]
如果每个单元都必须是唯一的，则可以对 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)
输出：
[['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']]
现在，每个部门单位都是独一无二的。
我有 4 个部门：
# department 1, 2, 3, 4
departments = ['d1','d2','d3','d4']
每个部门有8个单位：
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]
我需要创建工作组。
一个工作组由每个部门的 2 个单位组成，其中任何给定编号的单位只有一个人。总共 8 个单位，每个部门 2 个，必须包含 1 - 8 且没有重复的单位编号。
# 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)
感谢任何帮助，提前致谢。
您的方法很接近。这似乎是一个典型的回溯问题，对于每组单元，您都必须减少单元池。这是一个递归生成器函数：
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']
# ...
并且，一般情况：
>>> 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))（使用新生成器）是 2520，正好是 nCr(8, 2) * nCr(6, 2) * nCr(4, 2) * nCr(2, 2)，nCr 是 n-choose-r 或“n over r”。所以组合数算出来了 ;-)
稍微短一点的递归方法：
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))
输出：
2520
重要的是要注意上面的解决方案将产生单元在结果中重复的组合，即：
[['d11', 'd12', 'd23', 'd24', 'd35', 'd36', 'd47', 'd48'],
['d11', 'd12', 'd23', 'd24', 'd35', 'd37', 'd46', 'd48']]
如果每个单元都必须是唯一的，则可以对 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)
输出：
[['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']]
现在，每个部门单位都是独一无二的。