Abstract
The paper proposes a general approach to generating permutations that contain cycles, based on constructive tools introduced to describe combinatorial sets. Different generation problems for permutations of definite class are formulated and solved. A combinatorial set is introduced to define permutations represented as the multiplication of a definite number of cycles. For this set, combinatorial species and associated generating series are constructed.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
D. Knuth, The Art of Computer Programming, Vol. 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley (2005).
D. Knuth, The Art of Computer Programming, Vol. 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley (2005).
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC Press (1999).
M. Bona, Combinatorics of Permutations, Chapman Hall-CRC (2004).
F. Ruskey, Combinatorial Generation, Dept. of Comput. Sci., Univ. of Victoria, Canada, 1j-CSC 425/520 (2003).
J. F. Korsh and P. S. LaFollette, “Loopless array generation of multiset permutations,” The Comp. Journ., 47, No. 5, 612–621 (2004).
N. K. Timofeeva, “Features of formation and ordering of samples,” Cybern. Syst. Analysis, 40, No. 3, 460–466 (2004).
N. V. Semenova and L. N. Kolechkina, “A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements,” Cybern. Syst. Analysis, 45, No. 3, 438–445 (2009).
O. A. Yemets and Ye. M. Yemets, “A modification of the method of combinatorial truncation in optimization problems over vertex-located sets,” Cybern. Syst. Analysis, 45, No. 5, 785–791 (2009).
G. A. Donets and L. N. Kolechkina, “Method of ordering the values of a linear function on a set of permutations,” Cybern. Syst. Analysis, 45, No. 2, 204–213 (2009).
Yu. G. Stoyan and I. V. Grebennik, “Description of classes of combinatorial configurations based on mappings,” Dopovidi NAN Ukrainy, No. 10, 28–31 (2008).
R. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole (1986).
F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, University Press, Cambridge (1998).
H. S. Wilf, Generatingfunctionology, A K Peters, Ltd., Wellesley, MA (2006).
I. V. Grebennik and Yu. G. Stoyan, “Enumeration and constructive tools of generating special combinatorial sets,” Proc. 23rd Europ. Conf. on Oper. Res., Bonn, Germany (2009), p. 207.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 97–105, November–December 2010.
Rights and permissions
About this article
Cite this article
Grebennik, I.V. Description and generation of permutations containing cycles. Cybern Syst Anal 46, 945–952 (2010). https://doi.org/10.1007/s10559-010-9275-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-010-9275-1