Create unique combinations regardless of subset size-CodePudding

I am doing a project that requires getting unique combinations in Python regardless of the subset size.

Lets say I have a list of sizes [1,2,2,3,4,5] and a size bound of 8. I want combinations that have all the elements and no repeat such that the sum of each combination should be less than or equal to 8. Another restriction is that the subtraction of the sum and the bound should be minimum.

For example in this case the answer should be [5,3] [4,2,2] [3,1] this way the total waste out of 8 will be 4 which is (3 1)-8=4.

CodePudding user response：

You could use a recursive function to "brute force" the packing combinations and get the best fit out of those:

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))

output:

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]

This will take exponentially longer as your list of sizes gets larger but it may be enough if you only have very small inputs

CodePudding user response：

You probably need something like itertools.combinations, that will give you all the possible combinations of elements in sublists of given lenght without duplicate elements.

If you want to know more about function combinations, i would suggest to read also this.

Something like this should work:

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

This way you are getting all the combinations of myList, and printing those ones of which element's sum is 8.

A function like this may be useful:

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