Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

How to determine & record all possible variations for 5 items?

by Stenyj (Beadle)
on May 19, 2005 at 03:38 UTC ( #458506=perlquestion: print w/replies, xml ) Need Help??

Stenyj has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

I'm attempting to script a program that will allow me to evaluate something, based on the % of which each element makes up of the item.

Summary:
- 5 items
- Each item will have a %, and the total % of all 5 items together must equal 100%
- How can I estbalish a script to fill a table in a DB with every single possible outcome? The table would have 5 columns (one of each item) and the rows would simply have the % that each item was assigned (which would total 100 for each row)

NOTE: I'd ideally like to be able to chose to only allow increments of 2 or 5, to reduce the amount of outcomes (and thus, reduce the amount of time it would take the produce & record all possible outcomes).
So instead of:
100 0 0 0 0
99 1 0 0 0
98 2 0 0 0
etc. (and on and on and on)

I could specify it to do:
100 0 0 0 0
98 2 0 0 0
96 4 0 0 0
etc.

which would dramatically reduce the number of possibilities.

Any advice/suggestions etc. on how to approach this would be GREATLY appreciated.

I've started experimenting with tryign to figure out way to do this with nested loops, but am running into problems & I'm sure there must be a more efficient way.


Thank you for any feedback you may be able to provide!

Regards,
Stenyj
  • Comment on How to determine & record all possible variations for 5 items?

Replies are listed 'Best First'.
Re: How to determine & record all possible variations (AI::Prolog)
by Ovid (Cardinal) on May 19, 2005 at 04:31 UTC

    Well, if it's a one-off script, perhaps this is the time to learn Prolog, a language which does this sort of thing naturally:

    #!/usr/local/bin/perl use strict; use warnings; use AI::Prolog 0.65; my $by_two = AI::Prolog->make_list(map { $_ * 2 } 1 .. 50); my $by_five = AI::Prolog->make_list(map { $_ * 5 } 1 .. 20); my $prolog = AI::Prolog->new(<<"END_PROLOG"); member(X,[X|Tail]). member(X,[Head|Tail]) :- member(X, Tail). one_hundred(A,B,C,D,E) :- or(member(A, [$by_five]), member(A, [$by_two])), or(member(B, [$by_five]), member(B, [$by_two])), or(member(C, [$by_five]), member(C, [$by_two])), or(member(D, [$by_five]), member(D, [$by_two])), or(member(E, [$by_five]), member(E, [$by_two])), is(100, plus(A, plus(B, plus(C, plus(D, E))))). END_PROLOG $prolog->query('one_hundred(A,B,C,D,E).'); while (my $results = $prolog->results) { print join(',' =>@{$results}[1 .. 5]), $/; }

    Cheers,
    Ovid

    New address of my CGI Course.

      Wow! That's supposed to illustrate what Prolog is natural for? All I can say is Ack!
      And what would it take to modify it to generate vectors of 6 numbers instead of 5? Is there a parameter you could simply set?

        To be fair, my example is a bit more verbose than regular Prolog due to some parser limitations that I am currently working through. For example, the member/2 predicate is usually built in and doesn't need to be specified and the last line normally reads like this:

        100 is A + B + C + D + E.

        There are a few other things that would also clarify this code, but again, the parser is not yet where it should be. However, if you look at the code, you'll notice that I never told it how to find the answer. I just defined logically what the answer was and Prolog figured out how to arrive at it. If you read the code, it actually sounds fairly natural (particularly if you read my example below). It's easy to understand. Your's, on the other hand, is much less clear for me to understand from simply reading it.

        I'm also willing to bet that someone with more Prolog-fu than myself would be able to come up with a more concise solution. I just typed in what occurred to me.

        Update: And I could just put all of the numbers in one list. That makes the code simpler and faster:

        #!/usr/local/bin/perl use strict; use warnings; use AI::Prolog 0.65; my @numbers = grep { ! ($_ % 2) || ! ($_ % 5) } 1 .. 100; my $numbers = AI::Prolog->make_list(@numbers); my $prolog = AI::Prolog->new(<<"END_PROLOG"); member(X,[X|Tail]). member(X,[Head|Tail]) :- member(X, Tail). one_hundred(A,B,C,D,E) :- member(A, [$numbers]), member(B, [$numbers]), member(C, [$numbers]), member(D, [$numbers]), member(E, [$numbers]), is(100, plus(A, plus(B, plus(C, plus(D, E))))). END_PROLOG $prolog->query('one_hundred(A,B,C,D,E).'); while (my $results = $prolog->results) { print join(',' =>@{$results}[1 .. 5]), $/; }

        It's also worth noting what my solution can do that your solution cannot do. Tomorrow, your boss comes to you and says "yeah, great, but we just found out that the first and fourth numbers are always 4 and 45, respectively." So I change my query:

        $prolog->query('one_hundred(4,B,C,45,E).'); while (my $results = $prolog->results) { print join(',' =>@{$results}[1 .. 5]), $/; }

        I still get the right answers, but I didn't have to change my code (note that this still requires that the numbers be multiples of 2 or 5, because of the definition. It's trivial to alter, though.)

        Cheers,
        Ovid

        New address of my CGI Course.

Re: How to determine & record all possible variations for 5 items?
by jdporter (Chancellor) on May 19, 2005 at 04:10 UTC
    I tend to prefer a recursive approach for things like this; makes it easier to generalize. The following is kind of brute force, but I think it's correct:
    gen( 5, 50, 0, sub { print "@_\n" } ); sub gen { my( $cols, $max, $used, $found, @vec ) = @_; return $found->( @vec, $max-$used ) if $cols == 1; gen( $cols-1, $max, $used+$_, $found, @vec, $_ ) for 0 .. $max-$used; }
    Update: I passed 50 for the 'max' value here because it gives the result you want when going to 100 by 2's. Just multiply every number in every cell of the result by 2. Similarly, if you want to go to 100 by 5's, pass 20, and multiply all the numbers in the result by 5.
Re: How to determine & record all possible variations for 5 items?
by kvale (Monsignor) on May 19, 2005 at 04:09 UTC
    Here is a simple brute force enumeration for splitting 100 into 5 parts, each a multiple of 2:
    my $step = 2; for (my $a1 = 0; $a1 <= 100; $a1 += $step) { for (my $a2 = 0; $a2 <= 100-$a1; $a2 += $step) { for (my $a3 = 0; $a3 <= 100-$a1-$a2; $a3 += $step) { for (my $a4 = 0; $a4 <= 100-$a1-$a2-$a3; $a4 += $step) { my $a5 = 100-$a1-$a2-$a3-$a4; last if $a5 < 0; print "$a1 $a2 $a3 $a4 $a5\n"; } } } }
    If you want to get fancier, such as varying the number of parts, you may want to check out Algorithm::Loops

    -Mark

Re: How to determine & record all possible variations for 5 items?
by ivancho (Hermit) on May 19, 2005 at 04:50 UTC
    could you please specify what you mean by
    I'd ideally like to be able to chose to only allow increments of 2 or +5
    if you allow both increments at the same time, then any value after 3 ( = 5 * 2 - 5 - 2 ) is representable as a sum of 2's and 5's, so you might as well go the brute force way, with (0..100) without 1 and 3, cut up to current sum ( sorry, unclear here - basically, use, jdporter's solution, with generate_solutions(1, 100 ...
    buth with additional checks, ie,
    return if ($i == 1 || $i == 3)
    if you only want to allow 1 type of increment, say 5, then you might as well generate all partitions of 20 and multiply them by 5. The above solutions either give you only one increment, or, as in Ovid's allow only one of the two to be true, ie, 7 won't be a valid element..

    Rethinking further the part about both increments allowed. What about starting with an array (100,0,0,0,0), and then, from the right hand side, try to move either a 2 or 5 to the right, with backtracking recursion, printing any time you succeed without making a negative number. Hmm, but that would make it possible to shift a 2 from a 5, with a remaining 3, which is bad...

    Well, ok, I'll stop now.. the above idea, with just shifting 1's, should easily generate all unrestricted partitions of a number in a lexicographic order, so if you only needed 1 increment, it should suffice.. You can probably write the actual code for it faster than I.. in the meantime, I'll start thinking on generating weird restricted partitions...

Re: How to determine & record all possible variations for 5 items? (Haskell)
by kelan (Deacon) on May 19, 2005 at 14:59 UTC

    In the spirit of TIMTOLanguageTDI, here's a way to do it in Haskell:

    partition :: Integer -> Integer -> [[Integer]] partition total 1 = [[total]] partition total numparts = concat $ map (prepend) [total, (total - 1) .. 0] where prepend x = map (x:) (subpart x) subpart x = partition (total - x) (numparts - 1) -- then: partition 100 5
    Note that this will take a while, as there are over 4.5 million solutions. This doesn't take into account the "only multiples of 2 or 5" criteria, but it's easy to change it so that it does:
    partition :: Integer -> Integer -> [[Integer]] partition total 1 = [[total]] partition total numparts = concat $ map (prepend) numlist where prepend x = map (x:) (subpart x) subpart x = partition (total - x) (numparts - 1) numlist = filter twoorfive [total, (total - 1) .. 0] twoorfive x = x `mod` 2 == 0 || x `mod` 5 == 0
    And this gives about 600k solutions. Much more manageable.

    Another way to do it would be to create all possible lists of the desired length (5 in this case), with each element in a given range (0..100 here) and filter out the ones that don't sum to 100. I tried this approach as a mind exercise (you probably wouldn't want to use it because it would be very ineffecient). I got it to work, but only by hardcoding the number of elements to five, using a list comprehension. I know this is a Perl board, but anyone familiar with Haskell know of an easy and intuitive way to do something like:

    allLists :: Integer -> Integer -> [[Integer]] allLists n len = ?
    And allLists would return all lists of length len where each element is in the range 0..n?

Re: How to determine & record all possible variations for 5 items?
by jjohhn (Scribe) on May 19, 2005 at 03:49 UTC
    I think "integer partition" is the google phrase you want.
      This might help (and it might not) http://www2.toki.or.id/book/AlgDesignManual/WEBSITE/FILES/GEITIONS.HTM

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://458506]
Approved by monkfan
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2022-09-27 02:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer my indexes to start at:




    Results (118 votes). Check out past polls.

    Notices?