Therefore we have 2**K equally likely outcomes, each of which winds up with some sort order. And we have N! possible sort orders. Now can the sort orders possibly all come out even? The answer is no for N larger than 2 because if N is at least 3 then N! is divisible by 3, and therefore 1/N! has an infinite (repeating) decimal expansion while 1/2**K has a decimal expansion that terminates, therefore the actual probabilities of the buckets all have terminating expansions.
Which sort orders are favoured depends on the details of the sort algorithm.
Now if you want the idea of using a sort to scramble elements, you can do it with a Schwartzian sort. Like this:
Or use Fischer-Yates as often discussed.my @shuffled = map {$_->[1]} sort {$a->[0] <=> $b->[0]} map {[rand(), $_]} @orig;
BTW I am using infinite decimals vs non-infinite as a shortcut here to avoid talking about divisibility. This works because we talk about base 10, and 2 divides 10. But this is but one of a family of math arguments based on divisibility. For an example of another fun one, it is not hard to show that the Gregorian calendar has a number of days divisible by 7 but not 49. From that you can show, for instance, that the thirteenth of the month does not fall exactly evenly between the days of the week. It takes considerably more effort to figure out that the 13'th falls on Friday more often than straight chance would lead you to expect. :-)
In reply to Re (tilly) 2: random permutations
by tilly
in thread random permutations
by mave
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |