Finding all numbers which add up to another number

Discussion in 'Perl Misc' started by Jeffrey, Feb 16, 2006.

  1. Jeffrey

    Jeffrey Guest

    Hi everyone,
    I'm looking for a way to pass a number into a subroutine, and have it
    give back a list of all the ways that number can been added to get to
    that number.

    For example, if the function were to take 3 as a parameter it would
    give me back:
    1,1,1
    2,1
    3

    for 5 it would give back:
    1,1,1,1,1
    2,2,1
    3,2
    3,1,1
    4,1
    5
    2,1,1,1

    I haven't been able to come up with anything that does this the way I
    want:

    So far I did:
    &Sum(3)
    sub Sum {
    my $sum = shift;
    for (my $i=0; $i<=$sum; $i++) {
    for (my $j=0; $j<=$sum; $j++) {
    for (my $k=0; $k<=$sum; $k++) {
    if ($i+$j+$k == $sum) {
    print "[$i, $j, $k] \n";
    }
    }
    }
    }
    }

    But, that is hard-coded for $sum=3, it can't work with anything else.
    Also I would consider 0,0,3 to be the same as 0,3,0 and 3,0,0.

    Thanks for any ideas,
    Jeffrey
     
    Jeffrey, Feb 16, 2006
    #1
    1. Advertising

  2. Jeffrey wrote:
    > Hi everyone,
    > I'm looking for a way to pass a number into a subroutine, and have it
    > give back a list of all the ways that number can been added to get to
    > that number.


    to nail down the requirement, 1.5, 1.5 would NOT work?

    4, -1 would NOT work?

    i'm assuming you mean natural numbers...
     
    it_says_BALLS_on_your forehead, Feb 16, 2006
    #2
    1. Advertising

  3. Jeffrey

    DJ Stunks Guest

    it_says_BALLS_on_your forehead wrote:
    > Jeffrey wrote:
    > > Hi everyone,
    > > I'm looking for a way to pass a number into a subroutine, and have it
    > > give back a list of all the ways that number can been added to get to
    > > that number.

    >
    > to nail down the requirement, 1.5, 1.5 would NOT work?
    >
    > 4, -1 would NOT work?
    >
    > i'm assuming you mean natural numbers...


    and how big can the input number be? how many times can you add zero?
    when is your assignment due? :p

    anyhow, this is the type of problem which is naturally solved using
    recursion, rather than a stack of nested for's.

    -jp
     
    DJ Stunks, Feb 16, 2006
    #3
  4. Jeffrey

    Jeffrey Guest

    Sorry, I DO mean natural numbers, so -1 and 4 would not work, and 1.5
    and 1.5 would also not work.
     
    Jeffrey, Feb 16, 2006
    #4
  5. Jeffrey

    Paul Lalli Guest

    Jeffrey wrote:

    > I'm looking for a way to pass a number into a subroutine, and have it
    > give back a list of all the ways that number can been added to get to
    > that number.
    >
    > For example, if the function were to take 3 as a parameter it would
    > give me back:
    > 1,1,1
    > 2,1
    > 3
    >
    > for 5 it would give back:
    > 1,1,1,1,1
    > 2,2,1
    > 3,2
    > 3,1,1
    > 4,1
    > 5
    > 2,1,1,1


    Here's a small recursion-based program to get you started. Note that
    it will print out many duplicates. Removing them is left as an
    exercise to the reader.
    #!/usr/bin/perl
    use strict;
    use warnings;

    @ARGV == 1 or die "Usage: $0 <sum>\n";

    my @sums = sums($ARGV[0]);
    foreach my $sum (@sums){
    print "@$sum\n";
    }

    sub sums {
    my $num = shift;
    my @base = (1) x $num;
    return sums_helper(\@base);
    }

    sub sums_helper {
    my $parts_ref = shift;
    return unless @$parts_ref;
    my @these_sums;
    push @these_sums, [@$parts_ref];
    my $last = pop @$parts_ref;
    for my $i (0..$#$parts_ref){
    $parts_ref->[$i] += $last;
    push @these_sums, sums_helper([@$parts_ref]);
    $parts_ref->[$i] -= $last;
    }
    return @these_sums;
    }

    __END__

    Paul Lalli
     
    Paul Lalli, Feb 16, 2006
    #5
  6. Jeffrey

    Jeffrey Guest

    For my particular use of this, the number will always be less than 6,
    but there should still be a way to generalize this for any number.
    What do you mean how many times can you add zero?

    Thanks for the advice, I'll look into recursion.
     
    Jeffrey, Feb 16, 2006
    #6
  7. Jeffrey

    Jeffrey Guest

    Paul, that works amazing.

    Thank You,
    Jeffrey
     
    Jeffrey, Feb 16, 2006
    #7
  8. [A complimentary Cc of this posting was sent to
    Paul Lalli
    <>], who wrote in article <>:
    > > I'm looking for a way to pass a number into a subroutine, and have it
    > > give back a list of all the ways that number can been added to get to
    > > that number.
    > >
    > > For example, if the function were to take 3 as a parameter it would
    > > give me back:
    > > 1,1,1
    > > 2,1
    > > 3


    > Here's a small recursion-based program to get you started. Note that
    > it will print out many duplicates.


    I think this may be better; but it returns things in the opposite
    order to the requested one:

    #!/usr/bin/perl -w
    use strict;

    @ARGV == 1 or die "Usage: $0 <sum>\n";

    sub do_partitions_upto (&$$@) {
    my ($code, $sum, $limit, @pre) = @_;
    return $code->(@pre) unless $sum > 0;
    $limit = $sum if $limit > $sum;
    while ($limit > 0) {
    &do_partitions_upto($code, $sum - $limit, $limit, @pre, $limit);
    --$limit;
    }
    }

    sub do_partitions (&$) {
    my ($code, $sum) = @_;
    &do_partitions_upto($code, $sum, $sum);
    }

    do_partitions {print "@_\n"} $ARGV[0];

    __END__

    I checked that it gives a correct number of answers up to sum=60
    (966467 answers).

    Hope this helps,
    Ilya
     
    Ilya Zakharevich, Feb 16, 2006
    #8
  9. Jeffrey <> wrote:

    > What do you mean how many times can you add zero?



    If you don't restrict it, then it goes on for infinity:

    3 + 0
    3 + 0 + 0
    3 + 0 + 0 + 0
    ...


    --
    Tad McClellan SGML consulting
    Perl programming
    Fort Worth, Texas
     
    Tad McClellan, Feb 17, 2006
    #9
    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. Steven
    Replies:
    8
    Views:
    476
    Arndt Jonasson
    Feb 3, 2006
  2. Subra
    Replies:
    25
    Views:
    1,222
    user923005
    Mar 8, 2007
  3. Jekyll
    Replies:
    2
    Views:
    432
    Victor Bazarov
    Apr 24, 2007
  4. Deep Mehta via .NET 247
    Replies:
    2
    Views:
    452
    Dave A
    May 31, 2005
  5. Erik the Red
    Replies:
    4
    Views:
    181
    Chris Pine
    Jul 29, 2005
Loading...

Share This Page