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 abstract of this article has been published in the "Intellectual Archive Bulletin" , June 2012, ISSN 1929-1329.
The Library and Archives Canada reference page: collectionscanada.gc.ca/ourl/res.php?url_ver=Z39.88......
To read the article posted on Intellectual Archive web site please click the link below.