Cyril Prissette. An Algorithm to List All the Fixed-point Free Involutions on a Finite Set

Natural Sciences / Computer Science / Analysis of algorithms

Submitted on: Jun 11, 2012, 18:14:55

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 :

To read the article posted on Intellectual Archive web site please click the link below.


© Shiny World Corp., 2011-2023. All rights reserved. To reach us please send an e-mail to