面试题，使用递归解决排列组合问题

1. 面试题目

公司6人，3人一组，分组如下：

t1 = {"A","B","C"}     # 会唱歌
t2 = {"a","b","c"}     # 会跳舞

两两结合，表演节目。

其中A和a不能同一组（两个人有杀父之仇！）

同一组不能成对，比如AB，BC，ab等等

全体成员必须全部参加。

要求：打印所有组合。

2. 解题思路

1. 先找出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'}
   >>>
   

2. 排除杀父仇人组合

   >>> team_set - {'Aa','aA'}
   {'Bc', 'Bb', 'Ba', 'Ca', 'Cb', 'Ab', 'Cc', 'Ac'}
   

3. 递归调用选出合适的组合（核心部分）

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'}