Professional Web Applications Themes

All possible combinations of two lists - PERL Miscellaneous

I am trying to write a script to list all the possible combinations of gift certificate denominations for a given order total. For example, if a person has $25.00 to spend, they can purchase 1 $25.00 certificate, 2 $10.00 certificates and 1 $5.00 certificate, etc. The code I have so far is listed below. I am struggling with all of the possible combinations. I think I have to recurs through each of the items, but I can't figure out how to do that. Can anyone post some relevant sections in the docs, or other examples similar to this? use Data::Dump ...

  1. #1

    Default All possible combinations of two lists

    I am trying to write a script to list all the possible combinations of gift
    certificate denominations for a given order total. For example, if a person
    has $25.00 to spend, they can purchase 1 $25.00 certificate, 2 $10.00
    certificates and 1 $5.00 certificate, etc.

    The code I have so far is listed below. I am struggling with all of the
    possible combinations. I think I have to recurs through each of the items,
    but I can't figure out how to do that. Can anyone post some relevant
    sections in the docs, or other examples similar to this?

    use Data::Dump qw(dump);
    use strict;

    my denoms = sort { $a <=> $b } qw(25 10 5 50);
    my totals = qw(25 40);

    my %results;

    # Loop through each value
    foreach my $total_value (totals) {

    my %temp;
    my $remainder = $total_value;
    foreach my $denom (denoms) {

    # Check each denomination and see if it is evenly divisible.
    if ( ($total_value % $denom) == 0 ) {
    push({$results{$total_value}},
    { $denom => ($total_value/$denom) });
    }

    # Add one denomination to a local count
    if ($total_value > $denom) {
    $temp{$denom} += 1;
    $remainder -= $denom;
    }
    }
    push({$results{$total_value}}, \%temp) if ($remainder == 0);
    }
    print dump(\%results);


    Thanks
    -Ed W.


    Ed Guest

  2. #2

    Default Re: All possible combinations of two lists

    Ed W. wrote: 

    Your problem has little to do with Perl and you won't find anything in the
    doc's that is relevant to your problem.

    But it is a very famous example in computer science for an NP complete
    problem.
    Try to do some research on the knapsack problem. There are _many_ algorithm
    and ideas in computer literature about it.
    You should be able to adapt those solutions with almost no modification for
    your specific problem.

    jue


    Jürgen Guest

  3. #3

    Default Re: All possible combinations of two lists

    Ed W. wrote:

    (snipped)
     
     


    #!perl

    $purchase = "\$25.00";

    print "We offer gift certificates in amounts of \$5.00, \$10.00 ",
    "and \$25.00 for your needs. You may order any combination ",
    "of those gift certificates which total to a value of $purchase.";



    Purl Gurl
    --
    Rock Midis! Science Fiction! Amazing Androids!
    http://www.purlgurl.net/~callgirl/
    Purl Guest

  4. #4

    Default Re: All possible combinations of two lists

    Purl Gurl wrote:
     

    (snipped)
     [/ref]
     [/ref]
     
     
     


    There is additional humor in this beyond logical humor.

    You offer $5, $10, $25 and $50 gift certificates.

    I purchase $325 worth of gift certificates.

    How many 8 by 10 equivalent pages of html will I, a customer,
    have to scroll through to read all worded possible permutations
    generated by your code and code of others?


    Purl Gurl
    --
    Perl FAQs, Perl Doentation
    Apache FAQs, Apache Doentation
    http://www.purlgurl.net/
    Purl Guest

Similar Threads

  1. Possible combinations
    By girmalemu in forum Coldfusion - Getting Started
    Replies: 15
    Last Post: October 20th, 03:02 PM
  2. combinations
    By Rob Dixon in forum PERL Beginners
    Replies: 0
    Last Post: August 5th, 11:34 AM
  3. lists, attaching behaviour dynamiclly, update lists
    By crazy big fun in forum Macromedia Director Basics
    Replies: 0
    Last Post: June 28th, 06:20 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139