Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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

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


in reply to Easiest way to brute force generate all combinations of items within a hash?

"I've heard about some modules that can do Cartesian products...which is sort of what I want.."

Set::Scalar does...

Edit: better citing

Regards, Karl

«The Crux of the Biscuit is the Apostrophe»

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

Replies are listed 'Best First'.
Re^2: Easiest way to brute force generate all combinations of items within a hash?
by nat47 (Sexton) on Mar 01, 2015 at 22:06 UTC
    Thank, looking into this... Although I'd still like to know the easiest way to do this without a module.. Also, going to have to see if this can keep track of the sum of levels and Max weight constraints.
      "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»

        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

Log In?
Username:
Password:

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

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



    Results (100 votes). Check out past polls.

    Notices?