[go-nuts] rand.Perm() really random?

[⚖ Alexander "Surma" Surma]

Hi,

I wondered how the rand is able to generate these permutation arrays so fast,
so I took a look at the code:

func (r *Rand) Perm(n int) []int {
m := make([]int, n)
for i := 0; i < n; i++ {
m[i] = i
}
for i := 0; i < n; i++ {
j := r.Intn(i + 1)
m[i], m[j] = m[j], m[i]
}
return m
}

So, I see, that the array gets mixed - somehow. However:
Does this code actually distribute uniformly? Or is this some sort
of old, standard algorithm I'm gonna find in Knuth's TAOCP4?
It's not obvious to me - maybe someone can illustrate that for me.

Cheers,
Surma
--
Alexander "cussing-makes-my-arguments-even-more-valid" Surma

[⚖ Alexander "Surma" Surma]

Hi Michael,

> I'm not really well versed in statistics, but rand is totally
> deterministic, it's a pseudo-random number generator.
> So unless you seed it, something common is
> rand.Seed(time.Nanoseconds()), you'll have the same behaviour over all
> runs.
I am aware of that. I'm not suggesting that rand.Perm() is supposed to
be statistically random (actually, now that I write this, I realize
my subject implies this - well, never mind ;) )
What I acutally meant was: Is every possibled permutation (approx.)
equally likely?
As far as I know, with Intn() that's the case.

I'm totally not into security, so I don't care if these numbers are
actually random of if someone could reproduce them.

[Russ Cox]

> func (r *Rand) Perm(n int) []int {
>        m := make([]int, n)
>        for i := 0; i < n; i++ {
>                m[i] = i
>        }
>        for i := 0; i < n; i++ {
>                j := r.Intn(i + 1)
>                m[i], m[j] = m[j], m[i]
>        }
>        return m
> }
>
> So, I see, that the array gets mixed - somehow. However:
> Does this code actually distribute uniformly? Or is this some sort
> of old, standard algorithm I'm gonna find in Knuth's TAOCP4?
> It's not obvious to me - maybe someone can illustrate that for me.

It's an old, standard algorithm you're gonna find in Knuth's TAOCP2.
Knuth presents it as Algorithm P in Section 3.4.2 of Volume 2, crediting
it to Fisher and Yates (1938) and Durstenfeld (1964).

If Intn generates a uniformly distributed random integer from 1 to n,
then the code above generates a uniformly distributed random
permutation. At the beginning of each iteration, m[0:i] is a uniformly
distributed random permutation of the original m[0:i], and m[i:] is
just the original sequence. The loop body randomizes the location
of m[i] by swapping it with a randomly chosen location j in [0, i].

It's not a proof, but a good sanity check is to look at the sequence
of calls to Intn: Intn(1), Intn(2), Intn(3), ..., Intn(n). Taken as a whole,
there are 1*2*...*n = n! possible result sequences, which is equal to
the number of possible permutations we wanted to generate.

Of course, Intn does not generate truly random integers: it eventually cycles.
Knuth also mentions an article by Salfi (1974) that points out that if the
underlying random generator has a period m then you can't possibly
get a uniform distribution when n! > m because the generator can
only generate m different permutations. I'm not sure of the math
behind Intn, but it looks to me like the generator has 38,000 bits of
state. If all of that ends up contributing to the period then that's good
for generating uniform permutations of size up to n=3000 or so.
For uniformly distributed larger permutations where it is important
that every permutation is possible, you'd need to hook the algorithm to
a better random number generator.

Russ

[John C.]

> func (r *Rand) Perm(n int) []int {
> m := make([]int, n)
> for i := 0; i < n; i++ {
> m[i] = i
> }
> for i := 0; i < n; i++ {
> j := r.Intn(i + 1)
> m[i], m[j] = m[j], m[i]
> }
> return m
> }
>
> >
>

> What I actually meant was: Is every possible permutation (approx.)
> equally likely?

Yes.

Assume you have a uniformly random permutation array of size k. In
other words, m[i] = j with probability 1/k for all i,j in [0,k-1]. A
simple way to construct a uniformly random permutation array of size k
+1 would be as follows:

Add an entry to the end, m[k] = k. If we now swap m[k] with m[i]
using random i in [0,k], then it is easy to see that the new entry is
evenly distributed: m[k] = i with probability 1/(k+1) for all i in
[0,k]. As for the old entries, m[i] was left unswapped with
probability k/(k+1) and was swapped with probability 1/(k+1), so that
its value is now [0,k-1] with probability (1/k)*(k/(k+1) = 1/(k+1) and
its value is now k with probability 1/(k+1). Presto, you have a
uniformly random permutation array of size k+1!

The Rand.Perm(n) function builds up such an array starting with size 1
and growing until it reaches n.

John C.

[⚖ Alexander "Surma" Surma]

Oh, so very perspicuous :)
I must admit, I seem to have forgotten that this was mentioned in TAOCP2...

Thanks for your effort guys.

[roger peppe]

2010/5/25 Russ Cox <r...@golang.org>:

> For uniformly distributed larger permutations where it is important
> that every permutation is possible, you'd need to hook the algorithm to
> a better random number generator.

of course, that's dead easy, because Perm doesn't
rely on any particular generator.

it might be nice if some other types implemented
Int63 and Seed (even if the latter was just a no-op).
crypto/rc4 and crypto/rand spring to mind.

[Florian Weimer]

* John C.:

> Assume you have a uniformly random permutation array of size k. In
> other words, m[i] = j with probability 1/k for all i,j in [0,k-1].

That doesn't make it a uniformly distributed random permutation. If
you draw your array randomly from {[0, 1, 2], [1, 2, 0], [2, 0, 1]},
each with probability 1/3, it suffices your condition, but those
permutations aren't uniformly distributed.