Re: sum's break up

On Jul 26, 3:10 pm, Giovanni <blastingpro...@xxxxxxxxx> wrote:
Hi people,
I'm trying to implement an algorithm that, given an integer number N,
decomposes it in all its addenda so that their sum, is equal to the
number N.
i.e.
number 5:
1+1+1+1+1 OR 2+1+1+1 OR 3+1+1 OR 4+1 OR 2+2+1OR 3+2

I tryed to think in this way:
5
4 1
3 1 1
2 1 1 1
1 1 1 1 1

after i begin from 2nd line and I "explode" the number 4 decrementing
it and increasing the number at his right ( only if x[i]-1 > x[i+1])
3 2
2 2 1

This method works, but if I try to use it with 6, it "forgets" the sum
"2+2+2"

Has anyone an idea?

Here's how to do it in Python. The partition_generator creates all
permutations, such as (1,1,2) (1,2,1) and (2,1,1) which is what
_I_ normally use this for. But I can put them in a dictionary
to get combinations. It's more work, but I don't have a generator
that does combinations directly.

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:
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:
c = find_c()
if c < -1:
rollover(c)
yield sv
else:
move_col(c)
yield sv

# dictionary of unique partitions needed to
# take the permutaions created by partion_generator
# and make them combinations
u = {}
# target starting value
N = 7
for width in xrange(1,N+1):
# partition_generator returns a list
for p in partition_generator(N,width):
# deep copy list
pp = p[:]
# sort the copy (creates duplicates)
pp.sort()
# convert list to tuple (required for dictionary key)
t = tuple(pp)
# we'll count the duplicates...
if t in u:
u[t] += 1
else:
u[t] = 1
# ...but we're only interested in the keys
s = u.keys()
s.sort()
for t in s:
print t

## N = 6
## (1, 1, 1, 1, 1, 1)
## (1, 1, 1, 1, 2)
## (1, 1, 1, 3)
## (1, 1, 2, 2)
## (1, 1, 4)
## (1, 2, 3)
## (1, 5)
## (2, 2, 2)
## (2, 4)
## (3, 3)
## (6,)

## N = 7
## (1, 1, 1, 1, 1, 1, 1)
## (1, 1, 1, 1, 1, 2)
## (1, 1, 1, 1, 3)
## (1, 1, 1, 2, 2)
## (1, 1, 1, 4)
## (1, 1, 2, 3)
## (1, 1, 5)
## (1, 2, 2, 2)
## (1, 2, 4)
## (1, 3, 3)
## (1, 6)
## (2, 2, 3)
## (2, 5)
## (3, 4)
## (7,)




Tnx in advance to everybody ;-)


.

Relevant Pages
Quantcast