数理解析研究所講究録1093 巻 1999 年 5-10

5Generation of -permutations in $O(1)$ time perpermutation by reversing sublists$k$

三河賢治 (Kenji MIKAWA)

仙波 –郎 (Ichiro SEMBA)

Department of Computer Science, Ibaraki University{mikawa,} is. ibaraki. . jp$\mathrm{i}_{\mathrm{S}}\mathrm{e}\mathrm{m}\mathrm{b}\mathrm{a}$$@\mathrm{c}$$\mathrm{a}\mathrm{c}$Abstract
We discuss the problem of generating all -permutations of objects. Several papers have introduced a technique to alternatingly
reverse sublists of a listing for some combinatorial Gray codes in an
efficient manner. Our approach is to apply the technique to a listingof all -permutations of objects constructed recursively by reversing
sublists. We show that the list contains $n!/(n-k)!$ permutations sothat each string differs from its predecessor by the transposition of
two elements. It is easy to convert the construction to a recursive algorithm and then we develop the algorithm that produces successive
permutations in a constant amortized time per permutation.
$k$

$k$

1

$n$

$n$

Introduction

Many algorithms have been published for generating all permutations ofobjects and then there is a number of listings of successive permutations. Oneof the listings is the transposition order that is introduced independently byJohnson [3] and Trotter [11]. It is well-known that each permutation differs
by the transposition of adjacent elements.
Recently several interesting papers have been achieved for generating$n$some combinatorial Gray codes in a constant or constant amortized time
per object [1, 9, 5, 6, 8, 10, 2]. However, it is not trivial to generate a listing of combinatorial Gray codes in a unique manner. Most of those papers
managed to give a simple recurrence relation for combinatorial Gray codes.
Ruskey generalized a close relationship between some combinatorial Graycodes constructed recursively by reversing sublists [9]. To reverse certain
sublists seems to contribute a reduction of differences between successive
objects.

6

A -permutation of objects is an arrangement of the first objects
out of objects. First, we give a few modified definition for k-permutations
which are extended into length strings such that the set of all permutationsof objects contains the smaller set of the extended -permutations. Our
approach is to apply the reversing technique to such -permutations. Then alisting of all -permutations is obtained such that successive strings differ byalgorithm
the transposition of two elements. This paper presents afor generating them in a constant amortized time per string. It is obtained
directly from the recursively defined construction for -permutations. Notethat we do not count the time for printing permutations.
$k$

$k$

$n$

$n$

$n$

$k$

$n$

$k$

$k$

$\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{s}\mathrm{i}_{\mathrm{V}\mathrm{e}}$$k$Definitions and properties2

To begin with, we extend -permutations of distinct objects to strings oflength : a -permutation of length consists of elements which the firstelements are arranged in its original order and the rests are arranged ina lexical order. For example, if a string 52 is a 2-permutation of the set{1, 2, 3, 4, 5}, then its extension is 52134. When it will not lead to confusion,
we call them simply k-permutations.
The following useful notations are defined in [9]. If is a list of strings
denotes the list of strings obtained by appending
and is a symbol, then$\cdot L=312,321$ . If
an to each string of . For’ if $L=12,21$ , then 3
denotes the concatenation of the two lists. For
and $L’$ are lists thenexample, if $L=12,21$ and $L’=34,43$ , then $L\circ L’=12,21,34,43$ .
For a list , let first $(L)$ denote the first element on the list and let last $(L)$then denotes
denote the last element on the list. If is a list
in reverse order; i.e.,
the list obtained by listing the elements of$(L)$ and last
. Note the obvious equations first
$k$

$k$

$n$

$n$

$n$

$n$

$k$

$L$

$x\cdot L$

$x$

$L$

$x$

$\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{m}_{\mathrm{P}^{1\mathrm{e}}}.$$L\circ L’$

$L$

$L$

$L$

$l_{1},$$l_{2},$$\cdots,$$l_{n},$$\overline{L}$$\overline{L}=$$L$$l_{n},$$\cdots,$first$l_{2},$$(L)$$(\overline{L})=last$$l_{1}$$(\overline{L})=$.

.

length permutations in their original order and the other of which generates$n-k$ length permutations in a lexical order. The following construction isthe case for the original part. The list involves recursively defined sublists
which are alternatingly reversed.
$n$$\pi_{1}\cdot T_{k.1}$$.- \circ\pi_{n}-1^{\cdot}\mathrm{o}(n-1)\overline{n-1.)}\frac{\circ\pi_{2}\cdot\tau_{k-1}(}{\tau_{k-1}(n-1)}\pi_{n}Tk-1(n\mathrm{o}\cdots-1)$.

if odd$n$,$T_{k}(n)=\{$$\pi_{1}\cdot T_{k-}\ldots 1(\circ\pi_{n-1}\cdot T_{k1}^{\circ\pi_{2k}}n-1)\cdot\tau-1(n-(\overline{n-1)0\pi_{n}-1.)}\ldots\frac{\mathrm{o}}{T_{k-1}(n-1)}$

if even ,$n$

7and the case for the lexical part,$T_{k}(n)=\pi_{1}\cdot\tau k-1(n-1)$.

These are subject to the terminal condition that
. The construction
appends
to sublists in a lexical order from left to rightand each sublist is reconstructed with the set obtained by deleting a given
element and renumbering the rests from to. This constraint requiresthat permutations contain all distinct elements.
$T_{k}(0)=\emptyset$$\pi_{i}’ \mathrm{s}\in\{p_{1},p_{2}, \cdots,p_{n}\}$$\pi_{n-1}$$\pi_{1}$LEMMA 2.1 The list

$T_{k}(n)sati\mathit{8}fie\mathit{8}$the following $propertie\mathit{8}$:(1) $SucceS\mathit{8}ivek$ -permutations in $T_{k}(n)$ differ in exactly two$element\mathit{8}$.

(2) first $(T_{k}(n))=p_{1}p_{2}\cdots p_{n}$ .
(3) last $(.\tau k(n))=\{$$p_{n}p_{n-1}p_{1}p2\ldots p_{n-2}$

if odd$p_{n}p_{1}p2\ldots p_{n-1}$$otherwi\mathit{8}e$$n$and $k\geq 2$ ,.

Proof. The proof is by induction on . The list obviously has the statedproperties for $1\leq k\leq n\leq 2$ . Suppose that the lemma is true for $n\geq 3$ .
We must show it to be correct for $n+1$ . For convenience, we assume the ithelement in a permutation to be placed in the position $n-i$ , that is, the lastelement is placed in the position .
Obviously the list $T_{1}(n+1)$ contains $n+1$ permutations in which the
permutation is $p_{i}p_{1}\cdots pi-1pi+1\ldots p_{n+1}$ and the permutation differs from its
predecessor by two elements in positions and $n-i$ . Otherwise, for $k\geq 2$ ,the list contains $n+1$ sublists and we need to inspect the transpositionof successive permutations at the interface between the ith sublist
the(i+l)st sublist. The transposition behaves in different ways according to
the parities and .
The first case is for even . The
sublist is reverse and thesublist is natural. The contiguous permutations between the
sublist andthesublist differ by two elements, since thepermutation of thesublist is the lexically first one, as shown below.
$n$

$0$

$i\mathrm{t}\mathrm{h}$$n$$\mathrm{a}_{}\mathrm{n}\mathrm{d}$

$n$

$i$

$i$

$i\mathrm{t}\mathrm{h}$$(i+1)\mathrm{s}\mathrm{t}$$i\mathrm{t}\mathrm{h}$$(i+1)\mathrm{s}\mathrm{t}$$1\mathrm{a}s\mathrm{t}$$i\mathrm{t}\mathrm{h}$.
.
$\cdot$$p_{\nu}i.\overline{\tau_{k1}-(n)}$$\{$$\underline{p_{\dot{\mathfrak{g}}}}p_{1}\cdots p_{i-1}$$p_{i+1}$$p_{i+1}\cdot T_{k}-1(n)$$\{$$\underline{p_{i+1}}p_{i+2}\cdots p_{n+1}$$p_{1}\cdots p_{i-1}$$p_{i}p_{i+2}\cdots p_{n+1}$..

$\cdot$The underlined elements that are swapped appear in positions and $n-i$ .
When odd $n+1$ , this case occurs on the last interface. The third property$n$8holds, since the last permutation of $T_{k}(n+1)$ is
Is, $p_{n+1}p_{n}p1\ldots p_{n-1}$$p_{n+1}$.

. last$(\tau_{k-1}(n))$, thatsublist is natural and the
The second case is for odd . The
sublist is reverse. (1) When odd $n+1$ , the contiguous permutations between
sublist are shown below.
sublist and thethe$i$$(i+1)\mathrm{s}\mathrm{t}$$i\mathrm{t}\mathrm{h}$$(i+1)\mathrm{s}\mathrm{t}$$i\mathrm{t}\mathrm{h}$.

$p_{i}p_{1}\cdots p_{i-1}pi+1\ldots p_{n+1}$$p_{i}\cdot T_{k-1}(n)=$

$\{$

.
.
$\cdot$$\underline{p_{i}}p_{n+1}p1\ldots p_{i-1}$$p_{i+1}\cdot\overline{\tau_{k1}-(n)}=$

$\{$

..

$\underline{p_{i+1}}p_{i+2}\cdots p_{n}$$p_{i}p_{i+2}\cdots p_{n}$$p_{i+1}$$pn+1p1^{\cdot}$$p_{i+1}$$p_{1}\cdots p_{i}pi+2\ldots p_{n+1}$$p_{i-1}$

The underlined elements that are swapped appear in positions and $n-$
$i-1$ . (2) When even $n+1$ , we can give some formulae for detecting thetransposition of successive permutations at each interface. The successive
permutations at the last interface differ by the elements in positions and$n-1$ , as shown below.
$n$

$n$

$p_{n}p_{1}$$p_{n}\cdot T_{k-1(}n)$

$\{$

.

. .. $pn-1pn+1$.

$\cdot$$\underline{p_{n}}\underline{p_{n+1}}p_{1}\cdots p_{n-1}$$p_{n+1}$$p_{n+1k-}.\overline{\tau 1(n)}$

$\{$

.
.

$p_{n}p_{1}\cdots p_{n-1}$$\cdot$$p_{n+1}p_{1}$. .. $pn-1pn$

The last property holds in this case. Otherwise, for $i<n$ , the transposition
behaves in two different ways depending upon the value of . When $k=2$ ,the elements of permutations that appear in positions greater than 2 arearranged in a lexical order. The contiguous permutations between the
sublist are identical in arrangements as the ones for
sublist and thethe case (1), that is, the elements that are swapped appear in positions
and $n-i-1$ . When $k>2$ , they are shown below,$k$$i\mathrm{t}\mathrm{h}$$(i+1)\mathrm{s}\mathrm{t}$$n$$p_{i}p_{1}\cdots p_{i-1}p_{i+}1\ldots p_{n+1}$$p_{i}\cdot\tau_{k-1}(n)$$\{$:$\underline{p_{i}}p_{n+1}p_{n}p1\ldots p_{i-1}$$p_{i+1}$$p_{i+1}\cdot\overline{\tau_{k}-1(n)}$$\{$$\underline{p_{i+1}}p_{i+2}\cdots p_{n-1}$$p_{n+1}p_{n}p1\ldots p_{i-1}p_{i}p_{i+2}\cdots p_{n-1}$:$p_{i+1}$$p_{1}\cdots p_{i}pi+2\ldots p_{n+1}$

The elements that are swapped appear in positions and $n-i-2$ . The list
$T_{k}(n+1)$ has the stated properties. The proof is complete.
$n$$\blacksquare$

9

procedure interchange (: integer);begin
if
or notthen swap(n-l,n-i-l)odd(n)
else ifthen swap(n-l,n-i-2)
else ifthen swap(n-l,n-2)else ifthen swap
else swap (end {of procedure};$\mathrm{n},\mathrm{k},$$(\mathrm{k}=1)$$\mathrm{i}$$(\mathrm{o}\mathrm{d}\mathrm{d}(\mathrm{i}))$$\mathrm{i}=\mathrm{n}-1$$(\mathrm{n}-1,\mathrm{n}-\mathrm{i}-2)$$\mathrm{k}=2$

Figure 1: The procedure interchange
procedure gen (;var$\mathrm{n},\mathrm{k}$$\mathrm{n}-1,\mathrm{n}-\mathrm{i}^{-3)}$$(\mathrm{n},\mathrm{k}, \mathrm{i})$;.

: integer);$\mathrm{i}:\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r}$

begin
if
then
for
to
do begin
if odd(i) then gen(ifthen interchange$\mathrm{k}>0$$\mathrm{i}:=1$$\mathrm{n}$$\mathrm{n}-1,\mathrm{k}-_{1)}$$\mathrm{i}<\mathrm{n}$else;$\mathrm{n}\mathrm{e}\mathrm{g}(\mathrm{n}-_{1},\mathrm{k}-1)$;$(\mathrm{n},\mathrm{k}, \mathrm{i})$endend {of procedure};

Figure 2: The recursive procedure gen

3$(\mathrm{n},\mathrm{k})$.

Implementation and analysis

To begin with, we summarize the transposition of successive permutations
between the
sublist and thesublist and show it in a Pascal
procedure, in Figure 1. The procedure swap
swaps the elements inpositions and . The definition of the list $T_{k}(n)$ leads directly to a recursive algorithm for generating-permutations of objects. The Pascal
procedure gen
generates the list $T_{k}(n)$ , shown in Figure 2 and the procedure neg
is a symmetric procedure of gen
which generates thereversed.
Let us analyze the running time of gen. The procedure gen doesrecursive calls to either gen or neg in the while statement. We also knowthat it calls interchange once per loop and the interchange operation takes
a constant time to find the two elements that are swapped. Thus the total
amount of computations is proportional to the number of recursive calls,
which is $O(n!/(n-k)!)$ . To summarize above, the procedure gen generates
all -permutations in an amortized constant time to go from one string to
the next.
$i\mathrm{t}\mathrm{h}$$(i+1)\mathrm{s}\mathrm{t}$$(\mathrm{i},\mathrm{j})$

$i$

$j$

$\dot{\mathrm{a}}11k$$n$$(\mathrm{n},\mathrm{k})$$(\mathrm{n},\mathrm{k})$$(\mathrm{n},\mathrm{k})$$1\mathrm{i}_{\mathrm{S}\mathrm{t}}\overline{\tau_{k}(n)}$$(\mathrm{n},\mathrm{k})$

$n$

$k$

10

References[1] J. R. Bitner, G. Ehrlich, and E. M. Reingold, Efficient generation of the. Comput.
binary reflected Gray code and its applications, Comm.
Mach. 19 (1976), 517-521.
$A_{S\mathit{8}O}C$[2] B. Bultena and F. Ruskey, An Eades-McKay algorithm for well-formed
parentheses strings, to appear in Inform. Proc. Lett.
[3] S. M. Johnson, Generation of permutations by adjacent transpositions,Math. Comp. 17 (1963), 282-285.

[4] Y. Koda and F. Ruskey, A gray code for the ideals of a forest poset, J.
Algorithms 15 (1993), 324-340.
[5] J. Lucas, The rotation graph of binary tree is Hamiltonian, J. Algorithms
8 (1987), 503-535.

[6] J. Lucas, D. Roelants van Baronaigien, and F. Ruskey, On rotations
and the generation of binary trees, J. Algorithm815 (1993), 343-366.
[7] K. Mikawa and T. Takaoka, Generation of balanced parenthesis strings
in $O(1)$ time per string, submitted to J. Algorithms.
[8] A. Proskurowski and F. Ruskey, Binary tree Gray codes, J. Algorithms
6 (1985), 225-238.
[9] F. Ruskey, Simple combinatorial Gray codes constructed by revering
sublists, 4th ISAAC, Lecture Notes in Comput. Sci., Springer- Verlag,
761 (1993), 201-208.

[10] F. Ruskey and A. Proskurowski, Generating binary trees by transpositions, J. Algorithms 11 (1990), 68-84.
[11] H. F. Trotter, Algorithm 115: Perm, Comm. Assoc. Comput. Mach. 5(1962), 434-435.