[Tutor] Sort a list into equal sized chunks

[Kent Johnson]

Klas Marteleur wrote:
> Hi
> I have wrestled with a problem since last weeks knapsack discussion.
> 
> This is what i want, but i cant get it into a program.
> ----------------------------------------
> I have a sorted list (for example):
> aList = [10,9,8,7,6,5,4,3,2,1]
> 
> I have a max value (for example):
> maxValue=11
> 
> I have another list:
> anotherList=[]
> 
> After processing "aList" i want my "anotherList" to look like this:
> anotherList=[[10,1],[9,2],[8,3],[7,4],6,5]]
> were every element is as close to maxValue as possible.

As someone noted, this problem is properly called the bin packing problem. If you google for "bin 
packing problem" there are a number of interesting references. This one is easy to read:
http://www.ams.org/new-in-math/cover/bins1.html

Finding the optimal partition is a hard problem. But for your purposes (sorting files onto DVDs) a 
simple greedy algorithm might be sufficient. Here is a simple implementation of a First Fit 
Decreasing algorithm:

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


if __name__ == '__main__':
     import random

     def packAndShow(aList, maxValue):
         ''' Pack a list into bins and show the result '''
         print 'List with sum', sum(aList), 'requires at least', (sum(aList)+maxValue-1)/maxValue, 
'bins'

         bins = pack(aList, maxValue)

         print 'Solution using', len(bins), 'bins:'
         for bin in bins:
             print bin

         print


     aList = [10,9,8,7,6,5,4,3,2,1]
     packAndShow(aList, 11)

     aList = [ random.randint(1, 11) for i in range(100) ]
     packAndShow(aList, 11)


Kent