I need a more efficient algorithm for this problem.

Discussion in 'Ruby' started by Sam Kong, Jan 23, 2007.

  1. Sam Kong

    Sam Kong Guest

    Hi,

    I have a question which is not necessarily a ruby-related one.
    Anyway, I'm using Ruby for it.

    To make 5 by adding 2 more more natural numbers, there are different 6
    ways.

    1 + 1 + 1 + 1 + 1
    2 + 1 + 1 + 1
    2 + 2 + 1
    3 + 1 + 1
    3 + 2
    4 + 1


    In array form, you may express it like:

    [1,1,1,1,1]
    [2,1,1,1]
    [2,2,1]
    [3,1,1]
    [3,2]
    [4,1]


    Is there a general and efficient way to get the arrays?
    For example,

    set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]

    I came up with a mutual recursive solution but it's not very efficient.
    (Probably because it's recursive, which Ruby is not very good at.)
    I can't make it efficient for big numbers.
    I tried to use a cache but it didn't help much enough.

    def set n
    return [[1, 1]] if n == 2
    result = []
    (1...n).each do |i|
    subset = get_subset(n - i, i)
    subset.each do |j|
    result << + j
    end
    end
    result
    end

    def get_subset n, max
    result = (n <= max) ? [[n]] : []
    result += (set(n).select { |i| i.all? { |j| j <= max } })
    end


    Do you know a good solution to this problem?
    Also, is there a mathematical or algorithmic term for this problem like
    combinations and permutations?

    Thanks.

    Sam
     
    Sam Kong, Jan 23, 2007
    #1
    1. Advertising

  2. Sam Kong wrote:
    > Hi,
    >
    > I have a question which is not necessarily a ruby-related one.
    > Anyway, I'm using Ruby for it.
    >
    > To make 5 by adding 2 more more natural numbers, there are different 6
    > ways.
    >
    > 1 + 1 + 1 + 1 + 1
    > 2 + 1 + 1 + 1
    > 2 + 2 + 1
    > 3 + 1 + 1
    > 3 + 2
    > 4 + 1
    >
    >
    > In array form, you may express it like:
    >
    > [1,1,1,1,1]
    > [2,1,1,1]
    > [2,2,1]
    > [3,1,1]
    > [3,2]
    > [4,1]
    >
    >
    > Is there a general and efficient way to get the arrays?
    > For example,
    >
    > set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]
    >
    > I came up with a mutual recursive solution but it's not very efficient.
    > (Probably because it's recursive, which Ruby is not very good at.)
    > I can't make it efficient for big numbers.
    > I tried to use a cache but it didn't help much enough.
    >
    > def set n
    > return [[1, 1]] if n == 2
    > result = []
    > (1...n).each do |i|
    > subset = get_subset(n - i, i)
    > subset.each do |j|
    > result << + j
    > end
    > end
    > result
    > end
    >
    > def get_subset n, max
    > result = (n <= max) ? [[n]] : []
    > result += (set(n).select { |i| i.all? { |j| j <= max } })
    > end
    >
    >
    > Do you know a good solution to this problem?
    > Also, is there a mathematical or algorithmic term for this problem like
    > combinations and permutations?
    >
    > Thanks.
    >
    > Sam
    >

    I think it's called "partitions" and I think it's covered somewhere in
    Knuth's "Art Of Computer Programming". That's where I'd check first, anyhow.

    --
    M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P)
    http://borasky-research.blogspot.com/

    If God had meant for carrots to be eaten cooked, He would have given rabbits fire.
     
    M. Edward (Ed) Borasky, Jan 23, 2007
    #2
    1. Advertising

  3. Sam Kong

    stuart yarus Guest

    On 1/22/07, Sam Kong <> wrote:
    > Hi,
    >
    > I have a question which is not necessarily a ruby-related one.
    > Anyway, I'm using Ruby for it.
    >
    > To make 5 by adding 2 more more natural numbers, there are different 6
    > ways.
    >
    > 1 + 1 + 1 + 1 + 1
    > 2 + 1 + 1 + 1
    > 2 + 2 + 1
    > 3 + 1 + 1
    > 3 + 2
    > 4 + 1
    >
    >
    > In array form, you may express it like:
    >
    > [1,1,1,1,1]
    > [2,1,1,1]
    > [2,2,1]
    > [3,1,1]
    > [3,2]
    > [4,1]
    >
    >
    > Is there a general and efficient way to get the arrays?
    > For example,
    >
    > set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]
    >
    > I came up with a mutual recursive solution but it's not very efficient.
    > (Probably because it's recursive, which Ruby is not very good at.)
    > I can't make it efficient for big numbers.
    > I tried to use a cache but it didn't help much enough.
    >
    > def set n
    > return [[1, 1]] if n == 2
    > result = []
    > (1...n).each do |i|
    > subset = get_subset(n - i, i)
    > subset.each do |j|
    > result << + j
    > end
    > end
    > result
    > end
    >
    > def get_subset n, max
    > result = (n <= max) ? [[n]] : []
    > result += (set(n).select { |i| i.all? { |j| j <= max } })
    > end
    >
    >
    > Do you know a good solution to this problem?
    > Also, is there a mathematical or algorithmic term for this problem like
    > combinations and permutations?


    There are a few terms: partition function, number partitioning,
    integer partition,...

    There is a moderately large literature on the topic. Try googling.
    Wikipedia has some good introductory articles, like
    <http://en.wikipedia.org/wiki/Integer_partition>, and a number of
    references.

    >
    > Thanks.
    >
    > Sam
    >
    >
    >



    --
    Stuart Yarus

    <syarus at gmail dot com>
     
    stuart yarus, Jan 23, 2007
    #3
  4. On Jan 22, 2007, at 11:10 PM, Sam Kong wrote:

    > To make 5 by adding 2 more more natural numbers, there are different 6
    > ways.
    >
    > 1 + 1 + 1 + 1 + 1
    > 2 + 1 + 1 + 1
    > 2 + 2 + 1
    > 3 + 1 + 1
    > 3 + 2
    > 4 + 1


    > Is there a general and efficient way to get the arrays?


    You said you have a recursive solution. The first step to optimizing
    recursion is to make sure you aren't doing a bunch of unneeded work.
    For example, generating all the combinations and then removing
    duplicates is too much work. Instead, we want to make sure we
    recursively generate just one set of numbers:

    def partition(largest, rest = Array.new, &block)
    block.call([largest] + rest)
    (rest.first || 1).upto(largest / 2) do |i|
    partition(largest - i, + rest, &block)
    end
    end

    partition(5) { |nums| p nums }
    # >> [5]
    # >> [4, 1]
    # >> [3, 1, 1]
    # >> [2, 1, 1, 1]
    # >> [1, 1, 1, 1, 1]
    # >> [2, 2, 1]
    # >> [3, 2]

    The optimization for recursion is to eliminate the recursion. You
    can always unroll recursive code into an iterative solution:

    def partition(num)
    partitions = [[num]]

    until partitions.empty?
    current = partitions.shift

    yield current

    largest = current.shift
    (current.first || 1).upto(largest / 2) do |i|
    partitions << Array[largest - i, i, *current.dup]
    end
    end
    end

    partition(5) { |nums| p nums }
    # >> [5]
    # >> [4, 1]
    # >> [3, 2]
    # >> [3, 1, 1]
    # >> [2, 2, 1]
    # >> [2, 1, 1, 1]
    # >> [1, 1, 1, 1, 1]

    I translated these examples from the book Higher-Order Perl and, in
    case you are curious, wrote more about them here:

    http://blog.grayproductions.net/articles/2006/01/31/iterators-
    chapters-4-and-5

    Hope that helps.

    James Edward Gray II
     
    James Edward Gray II, Jan 23, 2007
    #4
  5. Sam Kong

    Sam Kong Guest

    Hi James,

    James Edward Gray II wrote:
    > On Jan 22, 2007, at 11:10 PM, Sam Kong wrote:
    >
    > > To make 5 by adding 2 more more natural numbers, there are different 6
    > > ways.
    > >
    > > 1 + 1 + 1 + 1 + 1
    > > 2 + 1 + 1 + 1
    > > 2 + 2 + 1
    > > 3 + 1 + 1
    > > 3 + 2
    > > 4 + 1

    >
    > > Is there a general and efficient way to get the arrays?

    >
    > You said you have a recursive solution. The first step to optimizing
    > recursion is to make sure you aren't doing a bunch of unneeded work.
    > For example, generating all the combinations and then removing
    > duplicates is too much work. Instead, we want to make sure we
    > recursively generate just one set of numbers:
    >
    > def partition(largest, rest = Array.new, &block)
    > block.call([largest] + rest)
    > (rest.first || 1).upto(largest / 2) do |i|
    > partition(largest - i, + rest, &block)
    > end
    > end
    >
    > partition(5) { |nums| p nums }
    > # >> [5]
    > # >> [4, 1]
    > # >> [3, 1, 1]
    > # >> [2, 1, 1, 1]
    > # >> [1, 1, 1, 1, 1]
    > # >> [2, 2, 1]
    > # >> [3, 2]
    >
    > The optimization for recursion is to eliminate the recursion. You
    > can always unroll recursive code into an iterative solution:


    Right. But some recursions are harder to unroll than others.^^

    >
    > def partition(num)
    > partitions = [[num]]
    >
    > until partitions.empty?
    > current = partitions.shift
    >
    > yield current
    >
    > largest = current.shift
    > (current.first || 1).upto(largest / 2) do |i|
    > partitions << Array[largest - i, i, *current.dup]
    > end
    > end
    > end
    >
    > partition(5) { |nums| p nums }
    > # >> [5]
    > # >> [4, 1]
    > # >> [3, 2]
    > # >> [3, 1, 1]
    > # >> [2, 2, 1]
    > # >> [2, 1, 1, 1]
    > # >> [1, 1, 1, 1, 1]
    >
    > I translated these examples from the book Higher-Order Perl and, in
    > case you are curious, wrote more about them here:
    >
    > http://blog.grayproductions.net/articles/2006/01/31/iterators-
    > chapters-4-and-5


    Your weblog looks very helpful.
    I just bookmarked it.

    >
    > Hope that helps.


    Yes. It helped a lot.
    >
    > James Edward Gray II


    Thank you very much.
    Also, I thank others who replied to my question.

    Sam
     
    Sam Kong, Jan 23, 2007
    #5
  6. "Sam Kong" <> wrote/schrieb <>:

    > Do you know a good solution to this problem?


    I let you decide if mine is a good solution:

    #\\\
    $cache = []

    def parts(s)
    if s < 1
    []
    else
    $cache ||
    begin
    a = []
    s.downto(1) do |n|
    k = s / n
    left = [].fill(n, (0 .. (k-1)))
    r = s - k * n
    if (r > 0)
    right = parts(r)
    right.each do |elem|
    a.push([left,elem])
    end
    else
    a.push(left)
    end
    end
    $cache = a
    end
    end
    end

    def part(n)
    parts(n).map{|x| x.flatten}
    end

    pp part(8)
    #///

    Regards
    Thomas
     
    Thomas Hafner, Jan 23, 2007
    #6
  7. On Jan 23, 2007, at 11:40 AM, Sam Kong wrote:

    > Hi James,
    >
    > James Edward Gray II wrote:
    >> You can always unroll recursive code into an iterative solution:

    >
    > Right. But some recursions are harder to unroll than others.^^


    You're not the first person to say that to me, but I still don't
    believe it. ;)

    Think of it this way. All recursion is doing for you is managing the
    call stack. You can always do that yourself.

    Just use an Array for the stack and put all the local variable in
    it. That's always works for unrolling recursion. Period.

    Frequently you can get away with much less too. In my example
    earlier in this thread, note that I didn't even need all the local
    values to unroll it.

    It just takes practice to think this way.

    James Edward Gray II
     
    James Edward Gray II, Jan 23, 2007
    #7
  8. Sam Kong

    Sam Kong Guest

    James Edward Gray II wrote:
    > On Jan 23, 2007, at 11:40 AM, Sam Kong wrote:
    >
    > > Hi James,
    > >
    > > James Edward Gray II wrote:
    > >> You can always unroll recursive code into an iterative solution:

    > >
    > > Right. But some recursions are harder to unroll than others.^^

    >
    > You're not the first person to say that to me, but I still don't
    > believe it. ;)
    >
    > Think of it this way. All recursion is doing for you is managing the
    > call stack. You can always do that yourself.
    >
    > Just use an Array for the stack and put all the local variable in
    > it. That's always works for unrolling recursion. Period.
    >
    > Frequently you can get away with much less too. In my example
    > earlier in this thread, note that I didn't even need all the local
    > values to unroll it.
    >
    > It just takes practice to think this way.


    I'll take your words.
    Thank you very much for your advice.:)

    >
    > James Edward Gray II


    Sam
     
    Sam Kong, Jan 23, 2007
    #8
  9. Sam Kong

    Sam Kong Guest

    Hi Thomas,

    Thomas Hafner wrote:
    > "Sam Kong" <> wrote/schrieb <>:
    >
    > > Do you know a good solution to this problem?

    >
    > I let you decide if mine is a good solution:
    >
    > #\\\
    > $cache = []
    >
    > def parts(s)
    > if s < 1
    > []
    > else
    > $cache ||
    > begin
    > a = []
    > s.downto(1) do |n|
    > k = s / n
    > left = [].fill(n, (0 .. (k-1)))
    > r = s - k * n
    > if (r > 0)
    > right = parts(r)
    > right.each do |elem|
    > a.push([left,elem])
    > end
    > else
    > a.push(left)
    > end
    > end
    > $cache = a
    > end
    > end
    > end
    >
    > def part(n)
    > parts(n).map{|x| x.flatten}
    > end
    >
    > pp part(8)
    > #///


    Yes. That's much better than the code I posted.
    Actually I've already tried that.
    But the problem is that even the cached version is not fast enough for
    my purpose.
    James's non-recursive code is not fast enough either.

    Probably, the solution to my problem is not just algorithm.
    I need to find a mathematical formula.

    See http://home.att.net/~numericana/data/partition.htm
    What I want is not the array of partitions but only the size of
    partitions.
    For example, the number of different ways to make 1000 is
    24061467864032622473692149727991.
    It's almost impossible to keep an array of that size.

    I'm satisfied with this thread of talks because it taught me some even
    if I couldn't find the answer.

    Thanks.

    Sam
     
    Sam Kong, Jan 23, 2007
    #9
  10. On Jan 23, 2007, at 2:50 PM, Sam Kong wrote:

    > Hi Thomas,
    >
    > Thomas Hafner wrote:
    >> "Sam Kong" <> wrote/schrieb
    >> <>:
    >>
    >>> Do you know a good solution to this problem?

    >>
    >> #///

    >
    > Yes. That's much better than the code I posted.
    > Actually I've already tried that.
    > But the problem is that even the cached version is not fast enough for
    > my purpose.
    > James's non-recursive code is not fast enough either.
    >
    > Probably, the solution to my problem is not just algorithm.
    > I need to find a mathematical formula.
    >
    > See http://home.att.net/~numericana/data/partition.htm
    > What I want is not the array of partitions but only the size of
    > partitions.
    > For example, the number of different ways to make 1000 is
    > 24061467864032622473692149727991.
    > It's almost impossible to keep an array of that size.
    >
    > I'm satisfied with this thread of talks because it taught me some even
    > if I couldn't find the answer.
    >
    > Thanks.
    >
    > Sam


    These are Catalan numbers which you can learn more about on Wikipedia
    [1] or MathWorld[2]. If you just need to know the number of
    solutions, both references give a formula.

    -Rob

    [1] http://en.wikipedia.org/wiki/Catalan_number
    [2] http://mathworld.wolfram.com/CatalanNumber.html

    Rob Biedenharn http://agileconsultingllc.com
     
    Rob Biedenharn, Jan 23, 2007
    #10
  11. Sam Kong

    Sam Kong Guest

    Hi Rob,

    Rob Biedenharn wrote:

    > These are Catalan numbers which you can learn more about on Wikipedia
    > [1] or MathWorld[2]. If you just need to know the number of
    > solutions, both references give a formula.
    >
    > -Rob
    >
    > [1] http://en.wikipedia.org/wiki/Catalan_number
    > [2] http://mathworld.wolfram.com/CatalanNumber.html


    Thank you for the information.
    That's almost what I was looking for.
    Catalan numbers are for combinatorics not for partitions in that the
    order of numbers is significant in combinatorics.
    Anyway, the documents will give me hints.
    And at least, now I know that Mathematica provides the function.
    I can install Mathematica if I need to.

    I'm trying to solve math problems in projecteuler.net .
    They are very helpful when you want to apply your coding skills to
    solving problems.
    (Similar to ruby quiz but more math-oriented.)
    Some problems require math knowledge, though. (Brute force won't help.)
    It's fun.
    I hope more Ruby programmers will join it and challenge.
    It shows staticstics which compares languages.
    There are not many ruby users there yet.

    Thanks again.

    Sam
     
    Sam Kong, Jan 23, 2007
    #11
  12. On 1/24/07, Sam Kong <> wrote:
    >
    > Thank you for the information.
    > That's almost what I was looking for.
    > Catalan numbers are for combinatorics not for partitions in that the
    > order of numbers is significant in combinatorics.


    You want the Stirling Numbers of the second kind, I think

    http://en.wikipedia.org/wiki/Stirling_number

    martin
     
    Martin DeMello, Jan 24, 2007
    #12
  13. Sean O'Halpin, Jan 24, 2007
    #13
  14. "Sam Kong" <> wrote/schrieb <>:

    > Yes. That's much better than the code I posted.


    Unfortunately my ``solution'' of
    <> is none, because it does not
    report all combinations, sorry. Here's a better approach:

    #\\\
    $cache = {}

    def parts(s,u)
    u0 = [s,u].min
    if u0 < 1
    []
    else
    i = (s-1)*s/2+u0-1
    $cache ||
    begin
    a = []
    u0.downto(1) do |n|
    r = s - n
    if (r > 0)
    parts(r,n).each do |elem|
    a.push([n, elem])
    end
    else
    a.push([n])
    end
    end
    $cache = a
    a
    end
    end
    end

    def part(n)
    parts(n,n).map{|x| x.flatten}
    end
    #///

    > Actually I've already tried that.
    > But the problem is that even the cached version is not fast enough for
    > my purpose.


    On my PC evaluation of parts(45) takes 11.53 seconds without cache,
    and 2.96 seconds with cache. But it's definitely not appropriate for
    calculating parts(1000). But you've already mentioned, that you need
    only the number of combinations, not the combinations itself. Many
    years ago at University I've been told that it's often better to solve
    the problem directly. Solving an arbitrary intermediate problem can
    make things worse or even impossible. Here the intermediate problem is
    ``calculate the list of combinations''. Some others are (numerics):

    - Don't calculate the inverse of a matrix. The original problem is
    probably a linear system of equations. Just solve that.

    - Never calculate the characteristic polynomial just to find the
    roots. Solve the Eigenvalue-problem directly.

    Regards
    Thomas
     
    Thomas Hafner, Jan 24, 2007
    #14
  15. Sam Kong

    Sam Kong Guest

    On Jan 24, 1:00 am, "Martin DeMello" <> wrote:
    > On 1/24/07, Sam Kong <> wrote:
    >
    >
    >
    > > Thank you for the information.
    > > That's almost what I was looking for.
    > > Catalan numbers are for combinatorics not for partitions in that the
    > > order of numbers is significant in combinatorics.You want the Stirling Numbers of the second kind, I think

    >
    > http://en.wikipedia.org/wiki/Stirling_number


    Wow, finally I've got what I've been looking for.
    Thanks.

    Sam
     
    Sam Kong, Jan 24, 2007
    #15
  16. Sam Kong

    Sam Kong Guest

    On Jan 24, 3:45 am, Thomas Hafner <> wrote:
    > "Sam Kong" <> wrote/schrieb <>:
    >
    > > Yes. That's much better than the code I posted.Unfortunately my ``solution'' of

    > <> is none, because it does not
    > report all combinations, sorry. Here's a better approach:
    >
    > #\\\
    > $cache = {}
    >
    > def parts(s,u)
    > u0 = [s,u].min
    > if u0 < 1
    > []
    > else
    > i = (s-1)*s/2+u0-1
    > $cache ||
    > begin
    > a = []
    > u0.downto(1) do |n|
    > r = s - n
    > if (r > 0)
    > parts(r,n).each do |elem|
    > a.push([n, elem])
    > end
    > else
    > a.push([n])
    > end
    > end
    > $cache = a
    > a
    > end
    > end
    > end
    >
    > def part(n)
    > parts(n,n).map{|x| x.flatten}
    > end
    > #///
    >
    > > Actually I've already tried that.
    > > But the problem is that even the cached version is not fast enough for
    > > my purpose.On my PC evaluation of parts(45) takes 11.53 seconds without cache,

    > and 2.96 seconds with cache. But it's definitely not appropriate for
    > calculating parts(1000). But you've already mentioned, that you need
    > only the number of combinations, not the combinations itself. Many
    > years ago at University I've been told that it's often better to solve
    > the problem directly. Solving an arbitrary intermediate problem can
    > make things worse or even impossible. Here the intermediate problem is
    > ``calculate the list of combinations''. Some others are (numerics):
    >
    > - Don't calculate the inverse of a matrix. The original problem is
    > probably a linear system of equations. Just solve that.
    >
    > - Never calculate the characteristic polynomial just to find the
    > roots. Solve the Eigenvalue-problem directly.


    Yes, you said it right.
    I didn't know that the combination grows that fast.
    Now I know what's right approach to the solution.

    Thanks.

    Sam

    >
    > Regards
    > Thomas
     
    Sam Kong, Jan 24, 2007
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    6
    Views:
    1,116
  2. Timasmith
    Replies:
    36
    Views:
    887
  3. KK
    Replies:
    1
    Views:
    313
  4. Niall Macpherson
    Replies:
    11
    Views:
    179
    Niall Macpherson
    Sep 20, 2004
  5. Replies:
    3
    Views:
    112
    Anno Siegel
    Jan 6, 2005
Loading...

Share This Page