习题 子集和问题-1:写出集合A = [5, -2, 4, 2]的所有子集。
1.定义一个函数get_sub(list),传入参数为一个列表list:
def get_subs(list): # 定义函数,传入一个参数
res = [] # 用于保存所有的子集
for i in range(2**len(list)): # 循环遍历从1到该集合长度的平方的所有整数
sub = [] # 用于保存一个子集
for j in range(len(list)): # 用于移位运算(方便移位的自增)
if (i >> j) % 2 == 1: # 移位运算,将二进制位作为传入参数list集合的倒序映射
sub.append(list[j]) # (7)0111,有1的部位表示子集中list[0]、list[1]、list[2]存在,list[3]不存在
res.append(sub) # 调用列表的append()方法将得出的子集添加到结果中
return res # 返回结果
2.在主函数中调用该函数:
if __name__ == "__main__": # 定义主函数
A = [5, -2, 4, 2] # 定义一个列表
list1 = get_subs(A) # 调用函数求子集和
print(list1) # 输出结果
3.最后的结果为:
[[], [5], [-2], [5, -2], [4], [5, 4], [-2, 4], [5, -2, 4], [2], [5, 2], [-2, 2], [5, -2, 2], [4, 2], [5, 4, 2], [-2, 4, 2], [5, -2, 4, 2]]
习题 子集和问题-2:写出集合A = [5, -2, 4, 2]中,子集和等于k(整数)的所有子集的集合。
1.定义一个函数get_sub_equals_sum(items, k),传入参数为一个集合items和一个整数k:
def get_sub_equals_sum(items, k): # 定义函数,传入两个参数
result = [] # 用于保存满足条件的子集
N = len(items) # 获得传入的集合items的长度
for i in range(2**N): # i从0~2的N次方循环(包括0,不包括2的N次方)
sub = [] # 定义一个列表,用于临时保存每个子集的元素
for j in range(N): # 可移位的范围是0~N(包括0,不包括N)
if(i >> j) % 2 == 1: # 右移位运算,二进制数最低位为1,则不能被2整除,所以该位置元素存在(右移j位,则在二进制数左边添加j个0,右边去掉j位)
sub.append(items[j]) # 当集合中对应的下标第j位元素存在,则被添加到sub中形成子集
if sum(sub) == k: # 调用sum(iterable)函数求可遍历的sub中所有元素的和(即子集和),若子集和等于k
result.append(sub) # 则将该子集添加到结果列表中
return result # 返回结果列表
2.在主函数中调用该方法求得结果:
if __name__ == "__main__": # 定义主函数
A = [5, -2, 4, 2] # 定义一个列表
list2 = get_sub_equals_sum(A, 2)
list3 = get_sub_equals_sum(A, 7)
3.输出结果为:
[[-2, 4], [2]]
[[5, -2, 4], [5, 2]]