[Tutor] Sort a list into equal sized chunks

[Kent Johnson]

Klas Marteleur wrote:
> Thanks Kent
> Your program does what i wanted to accomplish. But i dont really know why, and 
> that disturbs me. 
> 
> I guess its the class that confuses me. Could you or sombody else on this list 
> help me out by putting some words on what is happening in this program, and 
> in which order things are done?

OK, I'll try.

First I define a class to represent a bin of items. What are the characteristics of a bin? A bin 
contains the actual items, which are represented as a list. But a bin also has a sum, the total of 
its items. Keeping a running sum as a separate attribute lets me avoid computing the sums each time 
I want to know what it is.

This is a pretty good example of a simple class, for those listening in. A Bin has a state - its 
list of items and its sum - and two simple behaviors - adding an item and creating a string 
representation.

Let's try one out:

 >>> b=Bin()
 >>> print b
Bin(sum=0, items=[])
 >>> b.append(1)
 >>> print b
Bin(sum=1, items=[1])
 >>> b.append(10)
 >>> print b
Bin(sum=11, items=[1, 10])

I can access the sum and the item list directly:
 >>> b.sum
11
 >>> b.items
[1, 10]

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

Now define a function to do the actual bin packing. It takes two arguments - a list of the values to 
be packed, and the maximum sum allowed in a bin.

>>def pack(values, maxValue):

The algorithm works best with a sorted list. If your list is already sorted, you don't need this 
line. If you are using a version of Python older than 2.4, you need to write this differently.
>>     #values = sorted(values, reverse=True)

This is a list of Bins. Initially it is empty.
>>     bins = []
>>

Now start putting items into bins.
>>     for item in values:

Go through the Bins in order, looking for one that can hold the current item
>>         # Try to fit item into a bin
>>         for bin in bins:
>>             if bin.sum + item <= maxValue:

We found a Bin that has room, add the item to the bin and break out of the bin search loop
>>                 #print 'Adding', item, 'to', bin
>>                 bin.append(item)
>>                 break

This code will only be run if the for loop ran to completion - if it did NOT terminate with a break. 
That only happens if we didn't find a Bin with room for the item. So, let's make a new bin.
>>         else:
>>             # item didn't fit into any bin, start a new bin
>>             #print 'Making new bin for', item

Make a new bin
>>             bin = Bin()

Add the item to the bin
>>             bin.append(item)

Add the bin to the list of bins
>>             bins.append(bin)
>>

When we get here all the items have been placed in bins, we are done.
>>     return bins
>>
>>

This is test code
>>if __name__ == '__main__':
>>     import random
>>

Here is a function that packs a list into Bins and prints out the result. It is handy for testing.
>>     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
>>
>>

This is a simple test case
>>     aList = [10,9,8,7,6,5,4,3,2,1]
>>     packAndShow(aList, 11)
>>

Here is a bigger test case using a list of random numbers
>>     aList = [ random.randint(1, 11) for i in range(100) ]
>>     packAndShow(aList, 11)

HTH,
Kent