# 题目：
# 求在Rn中找出个数最少的一个子集，这个子集的所有元素的并集为U，要求U ∩ C = C，且U ∪ C = U，请写出求解这样的一个子集的通用算法。
R = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']
R1 = ['b', 'b', 'c', 'd', 'e', 'f', 'g']
R2 = ['b', 'c', 'd', 'g', 'k', 'l', 'm', 'n']
R3 = ['a', 'c', 'g', 'i', 'j', 'k', 'm', 'n']
R4 = ['a', 'c', 'd', 'f', 'g', 'i', 'j', 'k', 'm', 'n']
R5 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'n']
Rn = [R1, R2, R3, R4, R5]
C = ['b', 'b', 'd', 'g']
# -------------------------------------------------------------------------------------------------------------------
# 思路：
# 将C的集合与R1、R2…Rn的集合对比遍历对比，找出符合要求且元素数最少的Rn(可能是多个)
C_set = set(C) # 求出C的集合（即去重）
subset = [R] # 满足U∩C = C，且U∪C = U的目标子集初始化为R，命名为subset
for i in Rn: # 遍历Rn
for j in C_set: # 遍历C的集合，如果C集合中的每个元素都在子集中，则下一步，否则剔除
if j not in set(i):
break
else:
if len(i) < len(subset[0]): # 若该子集元素个数<subset中子集的元素个数，则清空subset，将该子集设为新的subset
subset = [[]]
subset[0] = i
elif len(i) == len(subset[0]): # 若该子集元素个数=subset中子集的元素个数，则将此子集添加到subset
subset.append(i)
print(subset) # 打印出满足条件的子集
最小子集问题
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- centos minimal 网络配置 在虚拟机上安装发现默认是命令行界面一路进行下去，最后发现是Minimal的...
- CSS3 transform rotate 深入 透视效果perspective(px) ...
