# Finding all numbers which add up to another number

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

1. ### JeffreyGuest

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

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...

3. ### DJ StunksGuest

> 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?

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
4. ### JeffreyGuest

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
5. ### Paul LalliGuest

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
6. ### JeffreyGuest

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
7. ### JeffreyGuest

Paul, that works amazing.

Thank You,
Jeffrey

Jeffrey, Feb 16, 2006
8. ### Ilya ZakharevichGuest

[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

Hope this helps,
Ilya

Ilya Zakharevich, Feb 16, 2006
9. ### Tad McClellanGuest

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