Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Randomly select values from array

by Xilman (Friar)
on May 16, 2010 at 09:26 UTC ( #840212=note: print w/replies, xml ) Need Help??


in reply to Randomly select values from array

I'm guessing that "selecting for of them" is a typo for "selecting four of them". If not, please post a correction. Note that there may not be a way to remove all the numbers from the array. What if all the elements are negative, or greater than 15 say?

Here is a sketch of just one way; there are many others, some of them more efficient by various metrics. First, sort the array randomly. Then see whether the first four elements sum to 15. If so, remove them. Keep going until you have an array with four or fewer elements or until you get bored. This code fragment performs the selection, testing and removal. Wrapping it in code to loop and, optionally, terminating the procedure is left as an exercise because I don't want to do all your work for you.

@data = sort {rand < rand} @data; $data[0]+$data[1]+$data[2]+$data[3] == 15 and push @stored, [splice @d +ata, 0, 4];
Paul

Replies are listed 'Best First'.
Re^2: Randomly select values from array
by BrowserUk (Pope) on May 16, 2010 at 17:36 UTC

    To emphasis how bad that sort-based "shuffle" is, consider that over a million shuffles of four values, 1/3rd of the possibilities are never chosen. And the rest are chosen so disproportionately that 'fairness' doesn't enter the equation:

    ++$h{ join'',sort{ rand() < rand() } 'a'..'d' } for 1 .. 1e6;; printf "$_ : %.2f%%\n", $h{$_} / 1e4 for sort keys %h;; abcd : 12.48% abdc : 12.47% bacd : 12.48% badc : 12.49% cabd : 3.15% cadb : 3.12% cbad : 3.14% cbda : 3.13% cdab : 6.26% cdba : 6.26% dabc : 3.13% dacb : 3.15% dbac : 3.13% dbca : 3.11% dcab : 6.26% dcba : 6.25%

    Contrast that with

    use List::Util qw[ shuffle ];; ++$q{ join'',shuffle 'a'..'d' } for 1 .. 1e6;; printf "$_ : %.2f%%\n", $q{$_} / 1e4 for sort keys %q;; abcd : 4.18% abdc : 4.12% acbd : 4.14% acdb : 4.20% adbc : 4.17% adcb : 4.18% bacd : 4.15% badc : 4.19% bcad : 4.17% bcda : 4.16% bdac : 4.17% bdca : 4.15% cabd : 4.14% cadb : 4.17% cbad : 4.19% cbda : 4.18% cdab : 4.19% cdba : 4.20% dabc : 4.17% dacb : 4.15% dbac : 4.16% dbca : 4.22% dcab : 4.14% dcba : 4.13%

    And the latter is more efficient to boot.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      heh, use an older Perl (or use sort '_quicksort';), and you get abcd : 100%! Talk about not random.
      A touch slow, but it works now:
      use Algorithm::Permute qw(permute); @a = 'a' .. 'd'; $afact = 1; $afact *= $_ for 2 .. @a; permute { $h{ join '', sort { rand() < rand() } @a } += 1 / $afact; } @a for 1 .. 1e5; # a million takes a couple minutes printf "$_ : %.2f%%\n", $h{ $_ } / 1e3 for sort keys %h;

        But why combine an O( N! ) algorithm with an O(N log N) algorithm, when Fischer-Yates is O(N)?

        List::Util::shuffle() does a million 4 way shuffles in less than 1 second.

      "To emphasis how bad that sort-based "shuffle" is, consider that over a million shuffles of four values, 1/3rd of the possibilities are never chosen. And the rest are chosen so disproportionately that 'fairness' doesn't enter the equation:"

      I must try to remember that some people have difficulty recognizing meiosis (not that I'm including BrowserUk in that list). My original post included the words: "some of them more efficient by various metrics".

      Oh well.

      Paul

        Oh. Please do include me in that. I had absolutely no idea what meiosis meant before you mentioned it. I'm still sure how it applies here.

        "some of them more efficient

        In the first instance, it wasn't about efficiency. Just the fact that it didn't work.

Re^2: Randomly select values from array
by ikegami (Pope) on May 16, 2010 at 17:06 UTC
    @data = sort {rand < rand} @data;
    is not guaranteed to work, much less return something random. Use List::Util's shuffle instead.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2020-05-28 22:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If programming languages were movie genres, Perl would be:















    Results (166 votes). Check out past polls.

    Notices?