Python求子集和问题

习题 子集和问题-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]]
上一篇:VBA:全选 全不选复选框


下一篇:vant中,van-dropdown-menu-item中open和close事件的顺序