Generating a random cyclic permutation (Q1110343)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Generating a random cyclic permutation |
scientific article; zbMATH DE number 4072409
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Generating a random cyclic permutation |
scientific article; zbMATH DE number 4072409 |
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
