P127: Group the elements of a set into disjoint subsets
指定分组数量和尺寸，将列表拆分成不相交的分组。给定列表、分组数量和尺寸，可行解不是唯一的。本题要求罗列出所有可行的拆分方式。
首先，设计测试用例。一个解如果满足以下三个条件即为可行解：
- 分组数量和尺寸满足约束
- 所有分组都不相交
- 分组中的所有元素都属于原列表
但如何判断其是否罗列了所有可行解呢？
「从一个列表中抽取指定数量元素」是组合问题，「将一个列表拆分为多个分组」则是将一系列「从一个列表中抽取指定数量元素」所有可行解进行排列（permutation）。
可能的组合数量公司如下，n为候选元素縂数，r是参与组合元素数量。
因为一系列「从一个列表中抽取指定数量元素」都是从前一次抽剩下的元素中抽取的，所以每一次组合的n和r都不同。假设，初始元素数量N，拆分为I组不相交的子集，每一子集的元素数量记为。 第次组合候选元素数量为，第次组合可行解的数量为。所有分组可行解的数量为：
完整的测试用例代码：
from python99.lists.p127 import group
import functools
import operator
def test_group():
l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
nums = [3, 5, 2]
actual = group(l, nums)
for resolution in actual:
# each possibility has correct number of groups
assert len(resolution) == len(nums)
for index, value in enumerate(nums):
# each group has correct number of elements
assert len(resolution[index]) == value
# all groups are disjoint
assert len(set(functools.reduce(
operator.concat, resolution, []))) == len(l)
# all elements are in origin list
assert functools.reduce(operator.and_, [e in l for e in functools.reduce(
operator.concat, resolution, [])], True) == True
total = 1
m = len(l)
for num in nums:
total = total * functools.reduce(operator.mul, range(m-num+1, m+1), 1)/functools.reduce(
operator.mul, range(1, num+1), 1)
m = m - num
# it includes all resolutions
assert len(actual) == total
上面已解释了，「指定分组数量和尺寸，将列表拆分成不相交的分组」等于将一系列「从列表中抽取指定数量元素」的可行解进行排列。所以，先使用P126中实现的combination求出每一个分组的可行解集。再对所有解集进行排列。排列需要「集合乘法」，可以用递归和双迭代List Comprehension实现。
代码实现：
# Group the elements of a set into disjoint subsets.
# a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons?
# Write a predicate that generates all the possibilities via backtracking.
from python99.lists.p126 import combination
# group l into len(nums) subsets, nums imply number of groups respectively
def group(l, nums):
if len(nums) == 1:
return [combination(l, nums[0])]
first_group = combination(l, nums[0])
return [[first_group_element] + remain_group_e
for first_group_element in first_group
for remain_group_e in group(list(set(l)-set(first_group_element)), nums[1:])
]