Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
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)

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Failed to generate a user instance of SQL Server. Only an integratedconnection can generate a user instance. Harlan Messinger ASP .Net 2 03-28-2010 06:51 PM
How to generate warnings when How generate a warning when int is converted to bool or vice versa? PengYu.UT@gmail.com C++ 3 04-06-2006 11:24 PM
How to generate variable labels for same component within a generate loop Weng Tianxiang VHDL 5 02-16-2006 01:45 PM
VBScript to generate strong WPA pre shared keys? Wireless Networking 1 11-15-2004 10:30 PM



Advertisments