Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re^4: Easiest way to brute force generate all combinations of items within a hash?

by davido (Cardinal)
on Mar 02, 2015 at 01:16 UTC ( #1118342=note: print w/replies, xml ) Need Help??

in reply to Re^3: Easiest way to brute force generate all combinations of items within a hash?
in thread Easiest way to brute force generate all combinations of items within a hash?

I wish I had written Set::Scalar, but it was written by Jarkko Hietaniemi. However, how it works is well documented in his book Mastering Algorithms with Perl. Somehow along the way I just became the module's maintainer, and frankly it hasn't required much in the way of maintenance since then. If I recall, it got handed off to me when I submitted a patch to Set::Bag.

The reason I requested an example of the data is because I felt that we would probably have a better hope of providing useful help if we knew what we had to work with.

I could be wrong, but it seems like the most efficient solution would be to generate permutations one at a time, and start adding. As soon as the summation of a given permutation exceeds the threshold, process it and move on to the next. There are plenty of examples of how to permute lists on the Internet, but Heap's algorithm seems to be an excellent choice, if using an existing CPAN solution is out of the question. Or study the code in Algorithm::Permute, or Algorithm::Loops (among others).

The following code is almost a literal translation of the Heap's Algorithm from the Wikipedia article I linked to above. I didn't spend time adapting the algorithm to a more Perlish style; it is more "C style" than Perl. But one change I made was to allow the caller to pass in a callback. In this code example I call the callback "process()". The OP could write his own process that simply sums up the weights in each iteration, and stops counting when a limit is reached... then do something with that set of elements. I'm kind of unclear on what he would want to put in process(); that part of the question didn't seem well enough described for me. But certainly whatever needs to be done could be done within the process callback. This code snippet does the hard part already; permuting.

use strict; use warnings; my @array = ( 'a' .. 'd' ); generate(\&process, scalar(@array), [@array] ); sub process { print join(' ', @{shift()}), "\n"; } sub generate { my( $code, $n, $array ) = @_; if( $n == 1 ) { $code->($array); } else { for( my($j,$i)=(0,1); $i <= $n; $i++ ) { generate( $code, $n - 1, $array ); if( $n % 2 ) { $j = 1; } else { $j = $i; } @{$array}[$j-1,$n-1] = @{$array}[$n-1,$j-1]; } } }

This algorithm (as with most good permutation algorithms) doesn't need to hold every permutation in memory at once; it just lets you process one permutation before moving on to generating the next one. Oh, and this does count as a "nested loops" solution too, though one of the "loops" is brought to us through the power of recursion.


Replies are listed 'Best First'.
Re^5: Easiest way to brute force generate all combinations of items within a hash?
by karlgoethebier (Monsignor) on Mar 02, 2015 at 10:38 UTC

    Thank you very much davido for your kind reply and good advice.

    I forgot that maintainer != author ;-)

    Best regards, Karl

    «The Crux of the Biscuit is the Apostrophe»

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1118342]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (7)
As of 2020-02-29 14:05 GMT
Find Nodes?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?

    Results (128 votes). Check out past polls.