1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Permutations in cyclic form</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Permutations in cyclic form">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Permutations in cyclic form">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Permutations.html#Permutations" rel="up" title="Permutations">
<link href="Permutation-Examples.html#Permutation-Examples" rel="next" title="Permutation Examples">
<link href="Reading-and-writing-permutations.html#Reading-and-writing-permutations" rel="previous" title="Reading and writing permutations">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Permutations-in-cyclic-form"></a>
<div class="header">
<p>
Next: <a href="Permutation-Examples.html#Permutation-Examples" accesskey="n" rel="next">Permutation Examples</a>, Previous: <a href="Reading-and-writing-permutations.html#Reading-and-writing-permutations" accesskey="p" rel="previous">Reading and writing permutations</a>, Up: <a href="Permutations.html#Permutations" accesskey="u" rel="up">Permutations</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Permutations-in-cyclic-form-1"></a>
<h3 class="section">9.8 Permutations in cyclic form</h3>
<p>A permutation can be represented in both <em>linear</em> and <em>cyclic</em>
notations. The functions described in this section convert between the
two forms. The linear notation is an index mapping, and has already
been described above. The cyclic notation expresses a permutation as a
series of circular rearrangements of groups of elements, or
<em>cycles</em>.
</p>
<p>For example, under the cycle (1 2 3), 1 is replaced by 2, 2 is replaced
by 3 and 3 is replaced by 1 in a circular fashion. Cycles of different
sets of elements can be combined independently, for example (1 2 3) (4
5) combines the cycle (1 2 3) with the cycle (4 5), which is an exchange
of elements 4 and 5. A cycle of length one represents an element which
is unchanged by the permutation and is referred to as a <em>singleton</em>.
</p>
<p>It can be shown that every permutation can be decomposed into
combinations of cycles. The decomposition is not unique, but can always
be rearranged into a standard <em>canonical form</em> by a reordering of
elements. The library uses the canonical form defined in Knuth’s
<cite>Art of Computer Programming</cite> (Vol 1, 3rd Ed, 1997) Section 1.3.3,
p.178.
</p>
<p>The procedure for obtaining the canonical form given by Knuth is,
</p>
<ol>
<li> Write all singleton cycles explicitly
</li><li> Within each cycle, put the smallest number first
</li><li> Order the cycles in decreasing order of the first number in the cycle.
</li></ol>
<p>For example, the linear representation (2 4 3 0 1) is represented as (1
4) (0 2 3) in canonical form. The permutation corresponds to an
exchange of elements 1 and 4, and rotation of elements 0, 2 and 3.
</p>
<p>The important property of the canonical form is that it can be
reconstructed from the contents of each cycle without the brackets. In
addition, by removing the brackets it can be considered as a linear
representation of a different permutation. In the example given above
the permutation (2 4 3 0 1) would become (1 4 0 2 3). This mapping has
many applications in the theory of permutations.
</p>
<dl>
<dt><a name="index-gsl_005fpermutation_005flinear_005fto_005fcanonical"></a>Function: <em>int</em> <strong>gsl_permutation_linear_to_canonical</strong> <em>(gsl_permutation * <var>q</var>, const gsl_permutation * <var>p</var>)</em></dt>
<dd><p>This function computes the canonical form of the permutation <var>p</var> and
stores it in the output argument <var>q</var>.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fpermutation_005fcanonical_005fto_005flinear"></a>Function: <em>int</em> <strong>gsl_permutation_canonical_to_linear</strong> <em>(gsl_permutation * <var>p</var>, const gsl_permutation * <var>q</var>)</em></dt>
<dd><p>This function converts a permutation <var>q</var> in canonical form back into
linear form storing it in the output argument <var>p</var>.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fpermutation_005finversions"></a>Function: <em>size_t</em> <strong>gsl_permutation_inversions</strong> <em>(const gsl_permutation * <var>p</var>)</em></dt>
<dd><p>This function counts the number of inversions in the permutation
<var>p</var>. An inversion is any pair of elements that are not in order.
For example, the permutation 2031 has three inversions, corresponding to
the pairs (2,0) (2,1) and (3,1). The identity permutation has no
inversions.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fpermutation_005flinear_005fcycles"></a>Function: <em>size_t</em> <strong>gsl_permutation_linear_cycles</strong> <em>(const gsl_permutation * <var>p</var>)</em></dt>
<dd><p>This function counts the number of cycles in the permutation <var>p</var>, given in linear form.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fpermutation_005fcanonical_005fcycles"></a>Function: <em>size_t</em> <strong>gsl_permutation_canonical_cycles</strong> <em>(const gsl_permutation * <var>q</var>)</em></dt>
<dd><p>This function counts the number of cycles in the permutation <var>q</var>, given in canonical form.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Permutation-Examples.html#Permutation-Examples" accesskey="n" rel="next">Permutation Examples</a>, Previous: <a href="Reading-and-writing-permutations.html#Reading-and-writing-permutations" accesskey="p" rel="previous">Reading and writing permutations</a>, Up: <a href="Permutations.html#Permutations" accesskey="u" rel="up">Permutations</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
