On Jul 1, 12:45 am, Mensanator <[EMAIL PROTECTED]> wrote:
> Here's an example.
> ...
> def partition_generator(depth,width):
>   """creates all partions of a given depth,widtth (depth>=width)
>   depth objects in width bins such that each bin has at least 1 object
>   this function is a generator (does comb(depth-1,width-1) partitions)
>
>   partition_generator(depth,width)
>   depth:  total inverse rule 1 count (p of 2**p)
>   width:  total inverse rule 2 count (q of 3**q)
>   sv:     sequence vector (the partition)
>   returns sequence vector [sv]
>   """
>   def move_col(c):
>     sv[c-1] += 1
>     sv[c] -= 1
>   def find_c():
>     i = -1
>     while i<0:
>       if sv[i]>1:
>         return i
>       i -= 1
>   def rollover(c):
>     move_col(c)
>     sv[-1] = sv[c]
>     sv[c] = 1
>   if depth<width:                # error
>     print 'depth',depth,'must be >= to width',width
>     return                       # kills generator
>   max_element = depth - width + 1
>   sv = [1 for i in range(width)]
>   sv[-1] = max_element
>   yield sv[:]                    # first partition
>   while sv[0]<max_element:       # rest are generated by this loop
>     c = find_c()
>     if c < -1:
>       rollover(c)
>       yield sv[:]   # must yield copy of sv, not sv
>     else:
>       move_col(c)
>       yield sv[:]

It's just an example I know, but you can write this much more
cleanly...

def partitions(n, length):
    """Generate all sequences of positive numbers of the given
    length that sum to n."""
    assert 0 < length <= n
    if length == 1:
        yield [n]
        return
    for i in xrange(1, n + 2 - length):
        for p in partitions(n - i, length - 1):
            yield [i] + p

--
Paul Hankin
--
http://mail.python.org/mailman/listinfo/python-list

Reply via email to