News for hackers. Stuff that matters.

Ask HN: algorithm to slice a number into parts

Posted by adm on Wednesday January 21, 2009 @06:09AM
from the ask-hn dept.
I am trying to write a algorithm to slice a number into parts; such that those slices add upto original number.

  e.g. n = (n1 + n2+ .. + nm)
  where n is number and m no of slices.

  n will be positive integer and m won't exceed 50.
Do you know any algorithm for this?

Edit: slices should be of distinct values.

( 14 comments | 6 points | on HN )
Re:Ask HN: algorithm to slice a number into parts by cperciva on Wednesday January 21, 2009 @06:15AM (#443080)
I think your problem description is missing something; otherwise n1 = n2 = n3 ... = n[m-1] = 1, nm = n - m + 1 is a trivial solution.
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by cperciva on Wednesday January 21, 2009 @07:23AM (#443125)
Edit: slices should be of distinct values.

In that case, [1, 2, 3, ... m - 1, n - m*(m-1)/2] is a trivial solution.

[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by inklesspen on Wednesday January 21, 2009 @07:05AM (#443106)
Is this your homework?
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by RiderOfGiraffes on Wednesday January 21, 2009 @08:09AM (#443158)
Edit: slices should be of distinct values.

You can't do it with positive integers if n<m(m+1)/2, or with non-negative integers if n<m(m-1)/2. If there is no restriction then there are, again, trivial solutions.

Why are you doing this? As someone else has said, this does smell of homework. If it is homework, then tell us what you've tried. If it isn't, then tell us what it's for.

You continue to underspecify your problem. What are you trying to achieve?

[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by RiderOfGiraffes on Wednesday January 21, 2009 @07:10AM (#443110)
As others have said, your problem as stated is trivial. Here's a degenerate solution:

    n1 = n2 = ... = n(m-1) = 0
    nm = n
I'm sure that's not what you want.

Here's another solution:

    n1 = n2 = ... = nm = n/m
I'm sure that's not what you want either.

Others have asked relevant questions. Assuming you want the numbers to be integers, and as equal as possible, then compute:

    k_min = floor(n/m)
    excess = n-k_min*m
All will be at least k_min. If they are all k_min, then you will have a total of k_min*m. You need an additional "excess", so assign them, one each, to the first bunch.

    n1 = k_min + 1
    ...
    n(excess) = k_min + 1
    n(excess+1) = k_min
    ...
    nm = k_min
If you want you can reverse this so that the larger ones come after. That's left as an exercise for the interested reader.

You could also put all the excess in one place, so you have

  n1 = n2 = ... = n(m-1) = k_min
  nm = k_min + excess
So really, it all depends on what you want.
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by VarunGupta on Wednesday January 21, 2009 @06:44AM (#443089)
There can be many ways to do so, one of them is already described by cperciva.

Another can be,

a) All Integers n1 = n2 = n3 =.....= n[m-1] = int(n / m) and nm = n - (n1 + n2 + n3 +.....+ n[m-1])

b) Floats n1 = n2 = n3 =.....= n[m] = n / m

I feel the problem can be more serious if you want the parts to be in certain fashion or distribution.

[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by gjm11 on Wednesday January 21, 2009 @07:26AM (#443129)
Sure (even with the distinctness requirement that wasn't originally there). n1=1, n2=2, ..., and nm = whatever's left. This will only work if n is at least 1+2+...+m = m(m+1)/2, but if that isn't true then there's no solution.
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by kurtosis on Wednesday January 21, 2009 @08:50AM (#443196)
if interested in integer partitions this python should do the job

def intpart(n):

    if n == 0:

        yield []

    for k in range(1,n+1):

        for p in intpart(n-k):

            yield [k] + p
i believe that this isn't truly integer partitions because it will count 4 = 1,1,2,1 and 1,1,1,2 as different partitions but that's all I can give you between breakfast and work.

see wikipedia for integer partiton or young tableau for more on these interesting objects

[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by wlievens on Wednesday January 21, 2009 @06:57AM (#443096)
Do n1, n2, ... have to have different values? Increasing values?
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by mooism2 on Wednesday January 21, 2009 @07:11AM (#443112)
n[i] = i for 1 <= i < m

n[m] = n - m.(m-1)/2

This is still fairly trivial.

I sense there are yet more requirements you're not telling us.

[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by kraemate on Wednesday January 21, 2009 @08:09AM (#443157)
protip: Use Generating functions. Piece of cake if you use them for this problem.
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by arstotel on Friday January 30, 2009 @05:46PM (#458858)
write an algorithm that compute the factorial of a given whole number
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by arstotel on Friday January 30, 2009 @05:58PM (#458876)
how to write an algorithm
[ Parent | on HN ]
Re:Ask HN: algorithm to slice a number into parts by alexkay on Wednesday January 21, 2009 @07:19AM (#443118)
http://stackoverflow.com/ is a good place for this kind of questions.
[ Parent | on HN ]