mardi 11 septembre 2018

Most and Least Favoured permutation in naive shuffle algorithm

Given a number N and an array containing 1 ... N , and a naive shuffle algorithm as given belows

P := [1, 2, ..., N]
for i in 1..N do
    j := rand(1, N)
    swap(P[i], P[j])

Here, rand(1, N) returns a uniformly random integer between 1 and N inclusive.

Is there a way to find out the most and least probable permutation generated by the above naive shuffle algorithm programmatically?




Aucun commentaire:

Enregistrer un commentaire