Cyril Prissette. An Algorithm to List All the Fixed-point Free Involutions on a Finite Set
Submitted on: Jun 11, 2012, 18:14:55
Natural Sciences / Computer Science / Analysis of algorithms
Description: An involution on a finite set is a bijection such as I(I(e))=e for all the element of the set. A fixed-point free involution on a finite set is an involution such as I(e)=e for none element of the set. In this article, the fixed-point free involutions are represented as partitions of the set and some properties linked to this representation are exhibited. Then an optimal algorithm to list all the fixed-point free involutions is presented. Its soundness relies on the representation of the fixed-point free involutions as partitions. Finally, an implementation of the algorithm is proposed, with an effective data representation.
The Library of Congress (USA) reference page : http://lccn.loc.gov/cn2013300046.
To read the article posted on Intellectual Archive web site please click the link below.