Generating a random cyclic permutation (Q1110343)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Generating a random cyclic permutation |
scientific article |
Statements
Generating a random cyclic permutation (English)
0 references
1988
0 references
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.
0 references
program correctness proof
0 references
algorithm
0 references
random cyclic permutation
0 references
