无论子集大小如何，都可以创建独特的组合

Question

我正在做一个项目，无论子集大小如何，都需要在 Python 中获得独特的组合。

假设我有一个尺寸列表 [1,2,2,3,4,5] 和一个 8 的尺寸界限。我想要包含所有元素且没有重复的组合，这样每个组合的总和应小于或等于8. 另一个限制是sum和bound的减法应该是最小的。

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

Answer 1

您可能需要 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

Answer 2

您可以使用递归函数来“强制”打包组合并从中获得最佳组合：

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]

随着您的尺寸列表变大，这将以指数级增长，但如果您只有非常小的输入，这可能就足够了

无论子集大小如何，都可以创建独特的组合

Create unique combinations regardless of subset size

python

math

combinations

permutation