http://www.perlmonks.org?node_id=1118316

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

I've got a hash with a number of items. Each item contains three characteristics: size, level, and ratio. The ratio is the relationship between the size and level. I want to generate all possible combinations of size while < maxSize (so not every item can be used together, they must be less than total size) and add up the total level of the items in each set that is combined.

Afterwards I'm looking for some of the worst and best level combinatinos that are possible to achieve.

I'm sure there must be a fairly quick way to do this in perl, but I'm not experienced enough to know.

If I didn't have these items in a hash I would initially think to write a nested for loop for each item I had, but that can't possibly be the best way to do this, right?

I've heard about some modules that can do Cartesian products... which is sort of what I want... However, I need to keep track of the Sum of a second hash element... And I am not interested in a worst combination being a single element with a low score. The goal is to get as close to the max weight as possible (&have a good level) Example data

my %list = ( 'player1' => {rating=> 10,weight=> 60, ratio=> .166}, 'player2' => {rating=> 12, weight=> 100, ratio=> .12}, 'player3' => {rating=> 4,weight=> 23, ratio=> .173913043}, 'player3' => {rating=> 2,weight=> 142, ratio=>}, 'player4' => {rating=> 3, weight=> 119,ratio=>}, 'player5' => {rating=> 1, weight=> 14, ratio=>}, );
(One example ould be that I can take a max weight of 200)
  • Comment on Easiest way to brute force generate all combinations of items within a hash?
  • Download Code

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

      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»

Re: Easiest way to brute force generate all combinations of items within a hash?
by LanX (Archbishop) on Mar 02, 2015 at 00:19 UTC
Re: Easiest way to brute force generate all combinations of items within a hash?
by davido (Cardinal) on Mar 01, 2015 at 22:11 UTC

    Can you demonstrate some sample, representative data, please?


    Dave

      Absolutely, some ratio are blank, I didn't type them in
      my %list = ( 'player1' => {rating=> 10,weight=> 60, ratio=> .166}, 'player2' => {rating=> 12, weight=> 100, ratio=> .12}, 'player3' => {rating=> 4,weight=> 23, ratio=> .173913043}, 'player3' => {rating=> 2,weight=> 142, ratio=>}, 'player4' => {rating=> 3, weight=> 119,ratio=>}, 'player5' => {rating=> 1, weight=> 14, ratio=>}, );