mercredi 17 août 2016

How to generate a pseudo-random involution?

The title says it all.

For generating a pseudo-random permutation, the Knuth shuffles can be used. An involution is a self-inverse permutation and I guess, I could adapt the shuffles by forbidding touching an element multiple times. However, I'm not sure whether I could do it efficiently and whether it generates every involution equiprobably.




Aucun commentaire:

Enregistrer un commentaire