Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

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

by karlgoethebier (Monsignor)
on Mar 01, 2015 at 22:21 UTC ( #1118326=note: print w/replies, xml ) Need Help??


in reply to Re^2: 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'd still like to know the easiest way to do this without a module..."

I don't know. Perhaps reading the sources of Set::Scalar and figuring out how davido did it is helpful.

Update: Assumed davido does something "easy" ;-)

My best regards, Karl

«The Crux of the Biscuit is the Apostrophe»

  • Comment on Re^3: Easiest way to brute force generate all combinations of items within a hash?

Replies are listed 'Best First'.
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

    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.


    Dave

      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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2019-06-25 05:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Is there a future for codeless software?



    Results (101 votes). Check out past polls.

    Notices?