1. 面试题目
公司6人，3人一组，分组如下：
t1 = {"A","B","C"} # 会唱歌
t2 = {"a","b","c"} # 会跳舞
两两结合，表演节目。
其中A和a不能同一组（两个人有杀父之仇！）
同一组不能成对，比如AB，BC，ab等等
全体成员必须全部参加。
要求：打印所有组合。
2. 解题思路
-
先找出2个组相互组合的所有情况
>>> t1 = {"A","B","C"} >>> t2 = {"a","b","c"} >>> team_set = {el1+el2 for el1 in t1 for el2 in t2} >>> team_set {'Bc', 'Bb', 'Ba', 'Ca', 'Cb', 'Aa', 'Ab', 'Cc', 'Ac'} >>> -
排除杀父仇人组合
>>> team_set - {'Aa','aA'} {'Bc', 'Bb', 'Ba', 'Ca', 'Cb', 'Ab', 'Cc', 'Ac'} 递归调用选出合适的组合（核心部分）
3. 核心代码实现
我们先来验证最简单的组合，比如下面这种：
# 给定一个集合，包含若干元素
set1 = {"a","b","c"}
# 如果从中选择1个元素，有以下这么多组合
[{"a"},{"b"},{"c"}]
我们再看看从3元素中两两组合：
# 给定一个集合，包含若干元素
set1 = {"a","b","c"}
# 如果从中选择1个元素，有以下这么多组合
rst = [{"a","b"},{"b","c"},{"a","c"}] # 肉眼可见，手动暴力组合得出的结果
# 1如果把原来的集合去除一个元素a，原来的集合变成
t1 = {"b","c"}
# 2如果从t1中选择1个元素有多少种组合呢
[{"b"},{"c"}] # 这是在上文中提到过，貌似如果从集合中选择1个进行组合，是最简单的
# 3现在我们把原来的a加入到每个元素中去
[{"a","b"},{"a","c"}]
# 4我们把t1中再去除一个元素b,原来的集合变成：
t2 = {"c"}
# 5从t2中选择1个元素进行组合
[{"C"}]
# 6现在我们把原来的b加入到每个元素中去
[{"b","c"}]
# 7 把1-6步得到的结果组合起来就是
[{"a","b"},{"b","c"},{"a","c"}] # 和我们肉眼所见，暴力组合一致
# 8 还有一种比较特殊的，比如从3个人中选择3个人
[{"a","b","c"}]
从上面的手动分析过程我们可以看到1-3步和4-6是重复的过程，那么可以封装成函数
def getRst(set,num):
if len(set) == 0: # 集合为空，直接返回空list
return []
if num == 1: # 从集合中选1个进行组合
return [{x} for x in set]
elif len(set) == num:
return [set] # 要组合的人数如果和集合一直，直接返回，比如2个人的集合要选择2个人
else:
list_sum = []
temp_set = set.copy()
for i in range(len(set)):
temp_el = temp_set.pop()
for item in getRst(temp_set,num - 1):
temp_item = item.copy()
temp_item.add(temp_el)
list_sum.append(temp_item)
return list_sum
4. 验证
把刚才排入不能在一起的人的组合放进去验证：
rst = {'Bc', 'Bb', 'Ba', 'Ca', 'Cb', 'Ab', 'Cc', 'Ac'}
for item in getRst(rst,3):
print(item)
# 结果如下：
{'Ac', 'Ab', 'Cb'}
{'Ac', 'Cb', 'Ca'}
{'Ac', 'Cb', 'Cc'}
{'Ac', 'Cb', 'Ba'}
{'Ac', 'Cb', 'Bc'}
{'Ac', 'Cb', 'Bb'}
{'Ab', 'Ca', 'Cb'}
{'Ab', 'Cc', 'Cb'}
{'Ab', 'Ba', 'Cb'}
....
从结果看，有1个人参与两次活动的情形，比如{'Ac', 'Cb', 'Bb'},如何去重呢，可以利用集合的属性
str_sum = ""
for item in {'Ac', 'Cb', 'Bb'}:
str_num += item
print(len(set(str_num)))
# 结果是5，说明有人参加了两次，有人没有参加
那么我们对每个集合都做上面的操作得到想要的结果：
rst = {'Bc', 'Bb', 'Ba', 'Ca', 'Cb', 'Ab', 'Cc', 'Ac'}
for item in getRst(rst,3):
str_sum = ""
for str in item:
str_sum += str
if len(set(str_sum)) == 6:
print(item)
# 结果如下：
{'Ac', 'Bb', 'Ca'}
{'Ac', 'Ba', 'Cb'}
{'Ab', 'Cc', 'Ba'}
{'Bc', 'Ab', 'Ca'}
