[Tutor] Sort a list into equal sized chunks
Kent Johnson
kent37 at tds.net
Sun Apr 17 22:11:21 CEST 2005
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
More information about the Tutor
mailing list