Python求子集和问题

本文主要是介绍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]]

这篇关于Python求子集和问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！