How to generate this list? (followup)

Discussion in 'Perl Misc' started by Bryan, Oct 2, 2003.

  1. Bryan

    Bryan Guest

    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
    Bryan, Oct 2, 2003
    #1
    1. Advertising

  2. Bryan

    Sam Holden Guest

    On Wed, 01 Oct 2003 23:38:34 GMT, 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!


    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
    Sam Holden, Oct 2, 2003
    #2
    1. Advertising

  3. Bryan

    Bob Walton Guest

    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, Oct 2, 2003
    #3
  4. Bryan

    Bob Walton Guest

    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
    Bob Walton, Oct 2, 2003
    #4
  5. 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)
    Jeff 'japhy' Pinyan, Oct 2, 2003
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rob Maris

    USB vhdl code (followup)

    Rob Maris, Aug 6, 2004, in forum: VHDL
    Replies:
    3
    Views:
    2,825
    Alex Gibson
    Aug 8, 2004
  2. David Waz...

    Machine.Config followup...

    David Waz..., Jul 3, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    396
    Yan-Hong Huang[MSFT]
    Jul 7, 2003
  3. mbs

    Followup: Newbee Question

    mbs, Apr 6, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    289
    James Hancock
    Apr 6, 2004
  4. David
    Replies:
    0
    Views:
    396
    David
    Aug 30, 2004
  5. Darrel
    Replies:
    5
    Views:
    1,264
    Karl Seguin
    Nov 11, 2004
Loading...

Share This Page