CODEWITHSUNDEEP
pythonpython-3.xsumcombinationspython-itertools
Lara
Lara

Reputation: 2236

Python itertools make combinations with sum

A customer of mine is a company that produces different pieces (in different sizes) of wood floor. They have a problem that when someone buys XXm² in wood floor, they have to box its pieces.

The box can handle a maximum sum of 220cm. The pieces starts from 30cm and goes up 5cm until a complete piece of 220cm.

What am I trying to achieve? The best combination of different pieces and sizes into the box that the bottom at least has to have a big piece, otherwise the box can "brake". Thats because the box needs a strong bottom to handle others pieces above.

Yeah, said that. Lets go to the code!

The customer inputs the pieces, something like that:

[220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
 90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]

And one of the best outputs would be:

['220', '170,50', '150,70', '145,75', '130,90',
 '125,95', '125,95', '115,105', '110,110', '90,90,40',
 '70,50,50,50', '60,60,50,50',]

I'm trying to use itertools:

from itertools import combinations
for i in range(1, 5): # Maximum 4 pieces
    for comb in combinations(customer_input, i):
        if sum(comb) <= 220 and sum(comb) >= 195:
            print(comb)

The firsts prints are:

(220,)
(170, 50)
(170, 50)
(170, 50)
(170, 50)
(170, 50)
(170, 50)

Seems like its going right but, its outputing the combination (170, 50) more the once. I think that one approach its to stop trying to make new combinations after a piece were used.

How can I achieve it?

Upvotes: 0

Views: 356

Answers (3)

javidcf
javidcf

Reputation: 59731

This is a way to do what I think you are trying:

from collections import Counter

# Generate all combinations up to n elements without repetitions
# with sum up to max_sum
def combs(p, n, max_sum):
    p = sorted(p, reverse=True)
    return _combs_rec(p, n, max_sum, 0, [], 0)

def _combs_rec(p, n, max_sum, idx, current, current_sum):
    if len(current) > 0:
        yield current_sum, tuple(current)
    prev = None
    if n > 0:
        for i in range(idx, len(p)):
            if p[i] != prev and  current_sum + p[i] <= max_sum:
                current.append(p[i])
                yield from _combs_rec(p, n - 1, max_sum, i + 1, current, current_sum + p[i])
                current.pop()
            prev = p[i]

# Input data
pieces = [220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
          90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]
max_group = 4
max_sum = 220

# Get maximum combinations
c = Counter(pieces)
while sum(c.values()) > 0:
    next_sum, next_comb = max(combs(c.elements(), max_group, max_sum))
    c.subtract(next_comb)
    print(f'{next_comb} Sum: {next_sum}')

Output:

(220,) Sum: 220
(170, 50) Sum: 220
(150, 70) Sum: 220
(145, 75) Sum: 220
(130, 90) Sum: 220
(125, 95) Sum: 220
(125, 95) Sum: 220
(115, 105) Sum: 220
(110, 110) Sum: 220
(90, 90, 40) Sum: 220
(70, 50, 50, 50) Sum: 220
(60, 60, 50, 50) Sum: 220

Note this does not necessarily give the optimal solution. Even though each iteration is doing a brute-force search for the best combination, it is still a greedy algorithm at heart. There is nothing guaranteeing that choosing the best combination each time will allow you to get the set of combinations with the smallest total slack. For that, you would have to search within the global space of partitions of the set of pieces.

Upvotes: 2

Ralf
Ralf

Reputation: 16515

This is not a code answer, but an idea to broaden your horizon.

This kind of problem can be approached as a optimisation problem known as Knapsack problem.

One approach to solve Knapsack could be to use dynamic programming (the wikipedia page I linked has a section about it). There are also a lot of tutorials on how to program something like that. For example, here is a freecodecamp tutorial for dynamic solution to Knapsack problem; it is NOT in Python, but the important part is to understand how to solve a problem of this kind.

I hope that gets you started in the right direction for an optimal code solution.

Upvotes: 1

sanyassh
sanyassh

Reputation: 8550

Using set is a straightforward solution to avoid duplicates:

customer_input = [220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
 90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]

from itertools import combinations
combs = set()
for i in range(1, 5): # Maximum 4 pieces
    for comb in combinations(customer_input, i):
        if sum(comb) <= 220 and sum(comb) >= 195 and comb not in combs:
            print(comb)
            combs.add(comb)

# part of output:
# (220,)
# (170, 50)
# (170, 40)
# (150, 70)
# (150, 60)
# (150, 50)
# (145, 75)

Upvotes: 1

Related Questions