Finding all numbers which add up to another number

J

Jeffrey

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
 
I

it_says_BALLS_on_your forehead

Jeffrey said:
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...
 
D

DJ Stunks

it_says_BALLS_on_your forehead said:
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
 
J

Jeffrey

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

Paul Lalli

Jeffrey said:
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
 
J

Jeffrey

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

Ilya Zakharevich

[A complimentary Cc of this posting was sent to
Paul Lalli
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
 
T

Tad McClellan

Jeffrey said:
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
...
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top