Velocity Reviews > Perl > How to generate this list? (followup)

# How to generate this list? (followup)

Bryan
Guest
Posts: n/a

 10-01-2003
Thanks all for the suggestions! I realized something though (sorry for
that) that may simplify things..

In fact, I don't care about the order of A B and C. But I do care about
the -sum-!

For example, if you have the following formula; AxByCz, where x is the
number of A's y is the number of B's, z is the number of C's...

If k = x + y + z, I need to find all possible x, y and z values whose
sum is equal to k.

So, if k = 3, I could have:
x y z
1 0 2
1 1 1
1 2 0
2 0 1
etc, etc, etc.

Sadly, I did not drink enough coffee today to see the quick way to do
this either... any help appreciated!

B

Sam Holden
Guest
Posts: n/a

 10-02-2003
On Wed, 01 Oct 2003 23:38:34 GMT, Bryan <(E-Mail Removed)> wrote:
> Thanks all for the suggestions! I realized something though (sorry for
> that) that may simplify things..
>
> In fact, I don't care about the order of A B and C. But I do care about
> the -sum-!
>
> For example, if you have the following formula; AxByCz, where x is the
> number of A's y is the number of B's, z is the number of C's...
>
> If k = x + y + z, I need to find all possible x, y and z values whose
> sum is equal to k.
>
> So, if k = 3, I could have:
> x y z
> 1 0 2
> 1 1 1
> 1 2 0
> 2 0 1
> etc, etc, etc.
>
> Sadly, I did not drink enough coffee today to see the quick way to do
> this either... any help appreciated!

A recursive solution seems simple enough (though if there is only
ever going to be X, Y, and Z then an iterative one is just as easy).

Something like (not tested, other than for syntax and with the one
case shown):

sub combs {
my \$elements = shift;
my \$count = shift;
my @result;
return [\$count] if \$elements == 1;
die "Elements must be positive" if \$elements < 1;
for my \$to_use (0 ... \$count) {
push @result, map {[\$to_use, @\$_]} combs(\$elements-1, \$count-\$to_use);
}
return @result;
}

my @results = combs(3,3); #X,Y,Z are 3 elements, and count=3.
print "x\ty\tz\n";
print join("\t", @\$_),"\n" for (@results);

--
Sam Holden

Bob Walton
Guest
Posts: n/a

 10-02-2003
Bryan wrote:

> Thanks all for the suggestions! I realized something though (sorry for
> that) that may simplify things..
>
> In fact, I don't care about the order of A B and C. But I do care about
> the -sum-!
>
> For example, if you have the following formula; AxByCz, where x is the
> number of A's y is the number of B's, z is the number of C's...
>
> If k = x + y + z, I need to find all possible x, y and z values whose
> sum is equal to k.
>
> So, if k = 3, I could have:
> x y z
> 1 0 2
> 1 1 1
> 1 2 0
> 2 0 1
> etc, etc, etc.
>
> Sadly, I did not drink enough coffee today to see the quick way to do
> this either... any help appreciated!
>
> B
>

Well, there are an infinite number of solutions to this unless you put
some constraints on the values of x y and z, like insisting they are all
non-negative (from your example, perhaps you mean x to be positive and y
and z to be non-negative?). One way would be to just brute-force it:

\$k=10;
for \$x(0..\$k){
for \$y(0..\$k){
for \$z(0..\$k){
print "x=\$x, y=\$y, z=\$z, sum=\$k\n" if \$x+\$y+\$z==\$k;
}
}
}

There might be a slighly more efficient or elegant way, but why waste
time on it when the computer can do it practically instantly anyway?

--
Bob Walton
Email: http://bwalton.com/cgi-bin/emailbob.pl

Bob Walton
Guest
Posts: n/a

 10-02-2003
Bryan wrote:

> Thanks all for the suggestions! I realized something though (sorry for
> that) that may simplify things..
>
> In fact, I don't care about the order of A B and C. But I do care about
> the -sum-!
>
> For example, if you have the following formula; AxByCz, where x is the
> number of A's y is the number of B's, z is the number of C's...
>
> If k = x + y + z, I need to find all possible x, y and z values whose
> sum is equal to k.
>
> So, if k = 3, I could have:
> x y z
> 1 0 2
> 1 1 1
> 1 2 0
> 2 0 1
> etc, etc, etc.
>
> Sadly, I did not drink enough coffee today to see the quick way to do
> this either... any help appreciated!
>
> B
>

Note that there are an infinite number of solutions unless you constrain
x y and z in some fashion, like perhaps non-negative integers. It
appears from your example you perhaps intend x to be positive and y and
z to be non-negative? Here's a brute force assuming all three to be
non-negative integers:

\$k=10;
for \$x(0..\$k){
for \$y(0..\$k){
for \$z(0..\$k){
print "x=\$x, y=\$y, z=\$z, sum=\$k\n" if \$x+\$y+\$z==\$k;
}
}
}

Given the speed of computers, it is not worth it to come up with
something more elegant or faster.

--
Bob Walton
Email: http://bwalton.com/cgi-bin/emailbob.pl

Jeff 'japhy' Pinyan
Guest
Posts: n/a

 10-02-2003
On Thu, 2 Oct 2003, Bob Walton wrote:

>\$k=10;
>for \$x(0..\$k){
> for \$y(0..\$k){
> for \$z(0..\$k){
> print "x=\$x, y=\$y, z=\$z, sum=\$k\n" if \$x+\$y+\$z==\$k;
> }
> }
>}
>
>Given the speed of computers, it is not worth it to come up with
>something more elegant or faster.

But you could at least give the program half a brain:

for \$x (0 .. \$k) {
for \$y (0 .. (\$k - \$x)) {
print "x=\$x, y=\$y, z=", \$k-\$x-\$y, ", sum=\$k\n";
}
}

--
Jeff Pinyan RPI Acacia Brother #734 2003 Rush Chairman
"And I vos head of Gestapo for ten | Michael Palin (as Heinrich Bimmler)
years. Ah! Five years! Nein! No! | in: The North Minehead Bye-Election
Oh. Was NOT head of Gestapo AT ALL!" | (Monty Python's Flying Circus)