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
In reply to Re^4: Easiest way to brute force generate all combinations of items within a hash?
by davido
in thread Easiest way to brute force generate all combinations of items within a hash?
by nat47
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |