Re^3: Algorithm RFC: fast (pseudo-)random shuffle with no repetition (requirements?)

yes, thanks I figured that out yesterday, but wanted to wait for a reply first.

If one allows to shuffle the 0 column , collisions are possible and one needs to check.

If it stays fixed it's always fine.

> (Very-pseudo) random,

well "randomness" is not self defining, there are plenty of paradoxes in math were people had different concepts of "random". °

For instance if you said you want

All legal permutations to be possible
And to be picked with the same likelihood

that's a pretty hard problem to be done fast.

I suppose many solutions here will produce certain permutations with a bigger probability. So please be explicit what kind of randomness you want.

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

see Wikisyntax for the Monastery}

°) classic example is roulette, the likelihood of a red or black number is always the same, even after a row of hundreds of reds. It's the likelihood of the red sequence which is low.

Comment on Re^3: Algorithm RFC: fast (pseudo-)random shuffle with no repetition (requirements?)

Replies are listed 'Best First'.
Re^4: Algorithm RFC: fast (pseudo-)random shuffle with no repetition (probability space) by LanX (Saint) on Sep 24, 2023 at 14:52 UTC
> So please be explicit what kind of randomness you want. Let's make the problem clearer with a constructed example. Let's suppose we need to test an app with random points on earth. First approach The point is calculated by randomly picking an first Y coordinate and than a legal X into 2D maps projecting of both hemispheres onto circles. Here an image of western and eastern hemisphere from Hemispheres_of_Earth This would be fundamentally flawed because there are far less legal X coordinates near the polar circle, IOW the result is biased b/c points in the equatorial region are underrepresented. Second approach Let's say we repeat Y,X picking randomly and only check afterwards till it's inside the circle. Now every point in the 2D projection has the same likelihood. But this is still flawed because the projection from 3D is flawed by itself. Third approach One way to guaranty that every square meter on earth has the same likelihood (if required) is to be pick polar coordinates (but only in a special way and ignoring that the earth is more a potato than a perfect sphere ) Combinatorics So far the geometrical example. But combinatorial structures from the OP are far more complicated. ° The random picking demonstrated so far in code examples in this thread will mostly be "flawed", because certain results will be far more likely than others. Some will even be skipped. I've put "flawed" in quotes for a reason. It's perfectly possible that imperfect random input is just good enough. That's why we need to ask "How random is random enough" Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery} °) A more obvious example is adding the results of two dices to construct a random number between 2 and 12. The result 6 =1+5 = 2+4 = 3+3 = ... would be totally overrepresented with a probabilty of 1/6 while 2 and 12 have only a probability of 1/36.	[reply]

Replies are listed 'Best First'.

Re^4: Algorithm RFC: fast (pseudo-)random shuffle with no repetition (probability space)
by LanX (Saint) on Sep 24, 2023 at 14:52 UTC

> So please be explicit what kind of randomness you want.

Let's make the problem clearer with a constructed example.

Let's suppose we need to test an app with random points on earth.

First approach

The point is calculated by randomly picking an first Y coordinate and than a legal X into 2D maps projecting of both hemispheres onto circles.

Here an image of western and eastern hemisphere from Hemispheres_of_Earth

This would be fundamentally flawed because there are far less legal X coordinates near the polar circle, IOW the result is biased b/c points in the equatorial region are underrepresented.

Second approach

Let's say we repeat Y,X picking randomly and only check afterwards till it's inside the circle. Now every point in the 2D projection has the same likelihood. But this is still flawed because the projection from 3D is flawed by itself.

Third approach

One way to guaranty that every square meter on earth has the same likelihood (if required) is to be pick polar coordinates (but only in a special way and ignoring that the earth is more a potato than a perfect sphere )

Combinatorics

So far the geometrical example.

But combinatorial structures from the OP are far more complicated. °

The random picking demonstrated so far in code examples in this thread will mostly be "flawed", because certain results will be far more likely than others. Some will even be skipped.

I've put "flawed" in quotes for a reason. It's perfectly possible that imperfect random input is just good enough.

That's why we need to ask "How random is random enough"

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

see Wikisyntax for the Monastery}

°) A more obvious example is adding the results of two dices to construct a random number between 2 and 12. The result 6 =1+5 = 2+4 = 3+3 = ... would be totally overrepresented with a probabilty of 1/6 while 2 and 12 have only a probability of 1/36.

[reply]