Re^8: Algorithm RFC: fast (pseudo-)random shuffle with no repetition

Darn!1!

> I count 7! = 5,040 solutions.

Of course you are right, what my my brain saw was that there is only one possible way to position the 1s.°

What I should better have shown is

(1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2)

which has only one solution

(1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1)

and 15! divided by 7! is still a very big number.

> I don't see mention in Algorithm::Permute of how it handles duplicate elements,

Assuming worst case means it's not handling duplicates differently. Many hear just use shuffle which certainly doesn't care.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

see Wikisyntax for the Monastery}

°) off by one permutation group ;)

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

Replies are listed 'Best First'.
Re^9: Algorithm RFC: fast (pseudo-)random shuffle with no repetition by karlgoethebier (Abbot) on Sep 24, 2023 at 18:45 UTC
`karl@h3002993:~/src/perl$ time ./pmute.pl 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 real 0m0,064s user 0m0,044s sys 0m0,005s` [download] ŤThe Crux of the Biscuit is the Apostropheť	[reply] [d/l]
Re^10: Algorithm RFC: fast (pseudo-)random shuffle with no repetition by LanX (Saint) on Sep 24, 2023 at 19:09 UTC
The 15 came from the OP, But as I said > If this doesn't convince you that try-and-error isn't a good idea, try adding even more 1s and 2s. for instance `((1)x 51, (2) x 50)` ==> `((101!) / (51!)) / (50!) = 1.99804427433e+29` Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re^11: Algorithm RFC: fast (pseudo-)random shuffle with no repetition by karlgoethebier (Abbot) on Sep 24, 2023 at 20:26 UTC
There is nothing I have to be convinced of. It was clear that with this method at some point end is. With ((1)x 9, (2) x 8) the red area begins on the relatively weak machine on which I tried this via IPad/SSH: 0m0,003s in the best and 0m41,493s in the worst case so far. With ((1)x 51, (2) x 50) that's completely hopeless there. With the OP's example (15), the result was actually quite acceptable - unlike ~~what he expected~~ predicted by him. ŤThe Crux of the Biscuit is the Apostropheť	[reply]