Re^2: Randomly select values from array

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%
[download]

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%
[download]

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.

RIP an inspiration; A true Folk's Guy

Comment on Re^2: Randomly select values from array Select or Download Code

Replies are listed 'Best First'.
Re^3: Randomly select values from array by ikegami (Patriarch) on May 16, 2010 at 17:51 UTC
heh, use an older Perl (or `use sort '_quicksort';`), and you get `abcd : 100%`! Talk about not random.	[reply] [d/l] [select]
Re^3: Randomly select values from array by blakew (Monk) on May 16, 2010 at 18:51 UTC
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;` [download]	[reply] [d/l]
Re^4: Randomly select values from array by BrowserUk (Patriarch) on May 16, 2010 at 19:11 UTC
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.	[reply] [d/l]
Re^5: Randomly select values from array by blakew (Monk) on May 16, 2010 at 19:37 UTC
I was shooting for humorous understatement, guess it wasn't obvious enough. I agree it's a horrible idea to actually use, I was just practicing to see why the original sort version doesn't work for myself.	[reply]
Re^3: Randomly select values from array by Xilman (Hermit) on May 17, 2010 at 08:04 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:" 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	[reply]
Re^4: Randomly select values from array by BrowserUk (Patriarch) on May 17, 2010 at 08:52 UTC
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.	[reply]