Generating a random cyclic permutation
We prove correct an algorithm that, given \(n>0\), stores in array b[0..n- 1] a random cyclic permutation of the integers in 0..n-1, with each cyclic permutation having equal probability of being stored in b. The algorithm was developed by Sattolo; our contribution is to present a more convincing proof using standard program-proving methods.
scientific article; zbMATH DE number 4072409