in reply to Re: Algorithm RFC: fast (pseudo-)random shuffle with no repetition
in thread Algorithm RFC: fast (pseudo-)random shuffle with no repetition

> It only found 240 different orders in 1e7 runs.

yes, there are only 240 = 10 * 4! distinct solutions for this one. qw/1 2 3 3 3 4 8/

EDIT

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.

update

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

  • Comment on Re^2: Algorithm RFC: fast (pseudo-)random shuffle with no repetition (constructive approach)
  • Select or Download Code