in reply to Re: Algorithm RFC: fast (pseudo-)random shuffle with no repetition
in thread Algorithm RFC: fast (pseudo-)random shuffle with no repetition
yes, there are only 240 = 10 * 4! distinct solutions for this one. qw/1 2 3 3 3 4 8/
There are 24= 4! possible permutations for lines 1,2,4 and 8
There are 10 possibilities to partition them into 4 groups to fill around the line 3s
(.)3(.)3(.)3(.)
where only the first and last partition is allowed to be empty, otherwise the 3 would collide.
(1)(2)(4)(8) ()(12)(4)(8) ()(1)(24)(8) ()(1)(2)(48) (12)(4)(8)() (1)(24)(8)() (1)(2)(48)() ()(1)(248)() ()(12)(48)() ()(124)(8)()
NB: since 1,2,4 and 8 are distinct they can't collide inside the fillers.
I think this constructive approach is the best way to allow all possible solutions to appear and with the same likelihood.
Because one only needs two random numbers rnd(24) and rnd(10) as "coordinates" to construct one.
Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery
|
|---|