Group number to create specified sum (galapagos?)


#1

I was wondering if it’s possible to group numbers into a list so that each list would have a sum close to a number i specified?

for example, i have numbers:
1,3,5,6,7,9,12
and i want a sum of list to be as close to 12 as possible
so it’d split these number into lists like:
[0] 12
[1] 9, 3
[2] 7, 5
[3] 6,1

is this possible?


(qythium) #2

That’s a combinatorial problem (more specifically 1-D bin packing), and I don’t think there’s a simple way to to express it in a form that can be directly accepted by Galapagos.

It’s definitely possible though, and there are lots of heuristics for solving these problems - you can google them, but they would definitely involve some scripting.


(qythium) #3

Here’s a simple Python implementation of “first fit decreasing” algorithm, copied directly from
https://bitbucket.org/kent37/python-tutor-samples/src/f657aeba5328/BinPacking.py?fileviewer=file-view-default

bin_packing.gh (6.8 KB)

''' Partition a list into sublists whose sums don't exceed a maximum 
    using a First Fit Decreasing algorithm. See
    http://www.ams.org/new-in-math/cover/bins1.html
    for a simple description of the method.
'''

    
class Bin(object):
    ''' Container for items that keeps a running sum '''
    def __init__(self):
        self.items = []
        self.sum = 0
    
    def append(self, item):
        self.items.append(item)
        self.sum += item

    def __str__(self):
        ''' Printable representation '''
        return 'Bin(sum=%d, items=%s)' % (self.sum, str(self.items))
        
        
def pack(values, maxValue):
    values = sorted(values, reverse=True)
    bins = []
    
    for item in values:
        # Try to fit item into a bin
        for bin in bins:
            if bin.sum + item <= maxValue:
                #print 'Adding', item, 'to', bin
                bin.append(item)
                break
        else:
            # item didn't fit into any bin, start a new bin
            #print 'Making new bin for', item
            bin = Bin()
            bin.append(item)
            bins.append(bin)
    
    return bins


from Grasshopper import DataTree
from Grasshopper.Kernel.Data import GH_Path
result = DataTree[float]()
for path, bin in enumerate(pack(values, maxValue)):
    result.AddRange(bin.items, GH_Path(path))