值总和包含在给定域中的项的子集

Question

我有一个元组集合：

items = (
    ('a', 7),
    ('b', 14),
    ('c', 21),
    ('d', 14),
    ('e', 7),
    ('v', 21),
    ('w', 14),
    ('z', 7) )

我想找到上述元组集合的所有可能子集，这些子集将小于第一个给定数，大于第二个给定数。到目前为止，我已经使用生成器生成了一个由元组中的值组成的子集列表，但是我想从上面的元组中生成一个字母子集，这些字母值或满足条件

到目前为止，我掌握的代码是：

import itertools

items = [
    ('a', 7),
    ('b', 14),
    ('c', 21),
    ('d', 14),]


def subsets(lst, target1, target2, c = []):
    if sum(c) <= target1 and sum(c) >= target2:
        yield list(c)
    else:
        for i in lst:
            if sum(c+[i]) <= target1:
                yield list(subsets(lst, target1, target2, c+[i]))

a = list(subsets(list(j[1] for j in items), 29, 20))
print(a)

我现在的输出

[7, 7, 7],
[7, 7, 14],
[7, 7, 14],
[7, 14],
[7, 21],
[7, 14],
[14, 7],
[14, 14],
[14, 14],
[21],
[14, 7],
[14, 14],
[14, 14]

The output I would like to have:

[a,a,a]
[a,a,b]
[a,a,d]
...

此外，我希望避免基于元素位置的重复，这意味着['d'，'b']和['b'，'d']是相同的，一次只能出现一次。现在，我可以看到我正在生成的值列表正在重复这一点

Answer 1

您可以检查每个子集的结果和，然后仅使用字母创建一个新列表

import itertools

items = [
    ('a', 7),
    ('b', 14),
    ('c', 21),
    ('d', 14),]

def subsetnew(lstnew, target1, target2):
    lstofsubsets =[]
    # check that lst new is not blank
    if lstnew:
        itemsnew =[] # get new list of all combinations
        for i in range(len(lstnew)):
            for j in itertools.combinations_with_replacement(lstnew, i):
                itemsnew.append(j)
                
        lstofsubsets = [] # new subset with only those that match
        for i in itemsnew:
            chckthesum =0
            onlyletterslst = []
            for jy in i:
                 chckthesum += jy[1]
                 onlyletterslst.append(jy[0])
            if target2< chckthesum and chckthesum <target1: # check of the sum against target values
                lstofsubsets.append(onlyletterslst)
                
        lstofsubsets.sort() #here you can sort the list of subsets
    return lstofsubsets


a = subsetnew(items,29,20)
print(a)

Answer 2

您已导入itertools，但未使用它。这里有一个^{}的解决方案

选取长度递增的组合，从1到max_elems，设置为upper_limit除以值中的最小数。（假设0和负数不作为值出现。）

def subsets(lst, upper_limit , lower_limit):
    max_elems = upper_limit // min(n[1] for n in lst)
    for num_elems in range(1, max_elems+1):
        for combination in itertools.combinations_with_replacement(lst, r=num_elems):
            total = sum(j[1] for j in combination)  # values, index 1
            if lower_limit <= total <= upper_limit:
                yield [j[0] for j in combination]  # letters, index 0

list(subsets(items, 29, 20))

输出：

[['c'],
 ['a', 'b'],
 ['a', 'c'],
 ['a', 'd'],
 ['b', 'b'],
 ['b', 'd'],
 ['d', 'd'],
 ['a', 'a', 'a'],
 ['a', 'a', 'b'],
 ['a', 'a', 'd'],
 ['a', 'a', 'a', 'a']]

（顺便说一句，ppl通常会执行(lower_limit, upper_limit)，而不是相反；但是我让您的函数调用保持原样。）

内循环中的另一个优化：

for combination in itertools.combinations_with_replacement(lst, r=num_elems):
    letters, numbers = zip(*combination)
    if lower_limit <= sum(numbers) <= upper_limit:
        yield letters  # or list(letters) if you don't want a tuple

---

要修改现有代码以包含字母，而不是执行j[1] for j in items，请直接使用j，以便它传入字母和值。只有在检查总和时，才使用[1]中的值。在subsets()函数中执行此操作非常重要，因为如果只使用结果执行此操作，则需要再次检查组合，，因为（7,7,7）可以是（'a'，'a'，'a'）或（'e'，'e'），也可以是'a'，'e'和'z'的所有组合，因为它们都是7。然后你需要过滤掉重复的