0

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.

martineau
  • 119,623
  • 25
  • 170
  • 301
cs499
  • 3
  • 1
  • 1
    You are looking for https://en.wikipedia.org/wiki/Bin_packing_problem where your final answer is `(no of bins)*bin_size - sum(list)` – Max Feb 06 '22 at 10:49
  • This is known as the [bin packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem). See [here](https://stackoverflow.com/questions/7392143/python-implementations-of-packing-algorithm) for a Python implementation of a greedy (inexact) solution, although the problem is NP-hard so all solutions are either exponential-time or approximate. – kcsquared Feb 06 '22 at 10:50

2 Answers2

0

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

Alain T.
  • 40,517
  • 4
  • 31
  • 51
-1

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
FLAK-ZOSO
  • 3,873
  • 4
  • 8
  • 28