创建唯一的组合，而不考虑子集大小

Question

我正在做一个项目，它需要在Python中获得唯一的组合，而不管子集大小如何。

假设我有一个大小为[1,2,2,3,4,5]的列表，大小界为8。我想要有所有元素且不重复的组合，使得每个组合的和应该小于或等于8。另一个限制是，和的界的减法应该是最小的。

例如，在这种情况下，答案应该是[5,3] [4,2,2] [3,1]，这样，8的总浪费将是4，即(3+1)-8=4。

Answer 1

您可以使用递归函数“蛮力”包装组合，并从这些组合中获得最佳匹配：

def pack(sizes,bound,subset=[]):
    if not sizes:                   # all sizes used
        yield [subset]              # return current subset
        return    
    if sizes and not subset:           # start new subset             
        i,m = max(enumerate(sizes),key=lambda s:s[1])
        subset = [m]                   # using largest size
        sizes  = sizes[:i]+sizes[i+1:] # (to avoid repeats)
    used = sum(subset)              
    for i,size in enumerate(sizes):    # add to current subset
        if subset and size>subset[-1]: # non-increasing order
            continue                   # (to avoid repeats)
        if used + size <= bound:
            yield from pack(sizes[:i]+sizes[i+1:],bound,subset+[size])
    if sizes:
        for p in pack(sizes,bound): # add more subsets
            yield [subset,*p]


def bestFit(sizes,bound):
    packs = pack(sizes,bound)
    return min(packs,key = lambda p : bound*len(p)-sum(sizes))

产出：

for p in pack([1,2,3,4,5],8):
    print(p,8*len(p)-sum(map(sum,p)))

[[5, 1], [4], [3, 2]] 9
[[5, 2, 1], [4, 3]] 1
[[5, 2], [4, 3, 1]] 1
[[5, 2], [4], [3, 1]] 9
[[5, 3], [4, 2, 1]] 1
[[5, 3], [4], [2, 1]] 9
[[5], [4, 1], [3, 2]] 9
[[5], [4, 2], [3, 1]] 9
[[5], [4, 3], [2, 1]] 9
[[5], [4], [3, 2, 1]] 9
[[5], [4], [3], [2, 1]] 17

print(*bestFit([1,2,3,4,5],8))
# [5, 2, 1] [4, 3]

print(*bestFit([1,2,3,4,5,6,7,8,9],18))
# [9, 1] [8, 4, 3, 2] [7, 6, 5]

当您的大小列表变得更大时，这将以指数方式花费更长的时间，但是如果您只有非常小的输入，这可能就足够了。

Answer 2

您可能需要类似于itertools.combinations的东西，这将使您在给定长度的子列表中提供所有可能的元素组合，而没有重复的元素。

如果您想了解更多关于函数combinations的信息，我建议您也阅读this。

像这样的事情应该有效：

for i in range(8//min(myList)):
    for j in itertools.permutations(myList, i):
        if sum(j) == 8:
            print(j)

这样，您就可以得到myList的所有组合，并打印元素之和为8的那些组合。

这样的函数可能是有用的：

def permutationsWithSum(myList: list[int], n: int):
    for i in range(n//min(myList)):
        for j in itertools.permutations(myList, i):
            if sum(j) == n:
                yield j