Generating a random cyclic permutation
type: Item
instance of: scholarly article
title: Generating a random cyclic permutation
zbMATH Open document ID: 0656.68076
DOI: 10.1007/BF01941134
author: David Gries
author: Jinyun Xue
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 4072409
zbMATH Keywords: program correctness proof
zbMATH Keywords: algorithm
zbMATH Keywords: random cyclic permutation
MaRDI profile type: Publication
cites work: Principles of combinatorics
description: scientific article; zbMATH DE number 4072409