Velocity Reviews > Perl > Finding all numbers which add up to another number

# Finding all numbers which add up to another number

Jeffrey
Guest
Posts: n/a

 02-16-2006
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

Guest
Posts: n/a

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

DJ Stunks
Guest
Posts: n/a

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

and how big can the input number be? how many times can you add zero?

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

-jp

Jeffrey
Guest
Posts: n/a

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

Paul Lalli
Guest
Posts: n/a

 02-16-2006
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
#!/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

Jeffrey
Guest
Posts: n/a

 02-16-2006
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
Guest
Posts: n/a

 02-16-2006
Paul, that works amazing.

Thank You,
Jeffrey

Ilya Zakharevich
Guest
Posts: n/a

 02-16-2006
[A complimentary Cc of this posting was sent to
Paul Lalli
<(E-Mail Removed)>], who wrote in article <(E-Mail Removed) .com>:
> > 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

Guest
Posts: n/a

 02-17-2006
Jeffrey <(E-Mail Removed)> 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
...

--
http://www.velocityreviews.com/forums/(E-Mail Removed) Perl programming
Fort Worth, Texas