(74.1) 1 から N までの数を並べ替えたもの、すなわち置換を、 辞書式順序で小さい順にすべて書き出すプログラムを書いてみよう。 それらは、 int 型の配列 a[1] から a[N] までに格納されているとする。
(74.2) 「1 2 3 4」の次は「1 2 4 3」だが、これだけを見ていてもよくわからない。
(74.3) もう少し N が大きい場合で考えよう。 「2 4 6 5 8 7 3 1」と、その次にくるものを並べてみよう。
左から３つの 2 4 6 は変化せず、 ４つめが 5 から 7 に変わっている。 まず、この「変化しない部分」と「変化する部分」の境目の位置 --- この例では 5 が a[4] なので、 その添え字の 4 --- を求めよう。
(74.4) それには、 「一番最後から戻ってみてくると、この 5 の手前までは単調増加である」 ことに注意すればよい。 だから、右の４つだけを並べ替えてもこれ以上大きなものは得られないのである。
(74.4) 次に、その 5 に代わるのは、それより右にあって、5 よりも大きい数のうち、 最小のもの --- ここでは 7 --- であることに注意する。
(74.5) その 5 と 7 とを入れ替えたものを間に書いてみよう。
すると、あとは、 入れ替えた 7 より右の「8 5 3 1」を反転させればよいことがわかる。
(74.6) まずは上の例の場合に正しく「次」を返すことを確かめつつ、 関数 next() を書こう。
#include <stdio.h>
#define N 8
int a[1+N]; /* a[0] は使わない。a[1] から a[N] を使う */
void print(void);
int next(void);
main() {
a[1] = 2; a[2] = 4; a[3] = 6; a[4] = 5;
a[5] = 8; a[6] = 7; a[7] = 3; a[8] = 1;
print();
next();
print();
}
void print(void) {
int i;
for (i = 1; i <= N; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
/*
a[1], ..., a[N] には 1 から N を並べ替えたものが代入されているとする。この関数
は、それらを、辞書式順序でその次に大きいものに並べ替えて返す。ただし、a[1] が 0
のときは 1, 2, ..., N で初期化する。次がある場合、初期化した場合は 1 を返す。次
がない場合、すなわち N, N-1, ..., 2, 1 のときは、a[ ] は変えないで 0 を返す。
*/
int next(void) {
int i, j, tmp;
if (a[1] == 0) { /* a[1] が 0 の場合は初期化する */
for (i = 1; i <= N; i++) {
a[i] = i;
}
return 1; /* 成功の印 1 を返す */
}
/* 以下、一般の場合 */
/* a[N] から逆に見てゆき、単調増加の限り戻る */
for (i = N; i > 0 && ???????; i--) {
;
}
if (i == ?) { /* もう次がないとき（最大のとき）は */
return 0; /* 失敗の印 0 を返す */
}
???? /* 上の例では i が 4（a[4] = 5 の添え字）に */
/* なるよう変える */
for (j = ??; ????; ????) { /* 上の例では j が 6（a[6] = 7 の添え字）に */
; /* なるよう変える */
}
??? = ???; ??? = ???; ??? = ???; /* a[i] と a[j] を交換する */
/* ここで、a[i] よりも右（a[i] は含まない）の順序を反転する */
return 1; /* 成功の印 1 を返す */
}
(74.7) うまくいったら、main() を
main() {
for (a[1] = 0; next() == 1; ) {
print();
}
}
に置き換え、N を 4 ぐらいにして、
置換がすべて出力されることを確かめよう。
(74.8) ※ wc は、入力の行数、単語数、文字数を出力するプログラムである。 wc とだけ打って起動した場合、適当に数行打ち込んでから、 行頭で Ctrl+D を押せば結果が出る。
(74.9) 「./a.out | wc」として動かすと、実行ファイル ./a.out の出力は画面には出ず、次の wc の入力となる。 これは「パイプ」と呼ばれる unix (linux) の機能である。
(74.10) N を 8 ぐらいにして実験する場合、出力全体を見るのは大変かもしれない。 そのときは、 上のようにして行数が N の階乗であることだけを確かめる方法もある。
(75.1) N×N のマスがある。 そこに、N 個の Q の文字を、次の条件を満たすように書き込む方法は何通りあるか？
N が 8 の場合を、「八人の女王」の問題という。
(75.2) チェスを知っている人は、チェス盤の上に八個のクイーンを置くと考え、 上の三つの条件をチェスのことばで言い直してみると、問題の意味がわかるだろう。
(75.3) N が 8 の場合を考えてみる。 64 のマスのうちの任意の 8 箇所に Q を置き、それから上の三つの条件を確かめる、 とすると、全部で 64C8 = 4426165368 通りとなり、 いまのコンピュータで扱うには多すぎる。
(75.4) 条件 1 から、どの行にもただ一つの Q が書かれていることがわかる。 第 i 行には左から a[i] マスめに Q が書かれているとすると、 条件 2 から、a[ ] は、 それを集合 {1, 2, ..., 8} からそれ自身への関数とみなしたときに全単射、 すなわち置換であることがわかる。 これなら、全部考えても 8! = 40320 通りで済む。
(75.5) ここで、前のセクションで書いた、 置換をすべて書き出すプログラムが使える。 main() を次で置き換えればよい。
main() {
int i, j;
for (a[1] = 0; next() == 1; ) {
for (i = 1; i <= N; i++) {
for (j = 1; j < i; j++) {
if (???) { /* ここに、(i, a[i]) と (j, a[j]) が斜め 45 度の線上にあるための条件を書く */
goto failed;
}
}
}
print();
failed:
;
}
}
(75.6) goto とラベルが出てきた。 goto は、そこへくると、 その次に書かれた文字列（ここでは failed） の後ろにコロン「:」がついた、ラベルと呼ばれるところへ飛ぶ。 ラベルの後ろには文がないといけないので、ここでは空文「;」を置いてある。 （「goto failed;」の最後のセミコロンは、 Ｃ言語の文の最後にいつもつく、あのセミコロンである。 また、ラベルは、上のように、行の先頭に書く。いわば、インデント（字下げ）の例外である。）
(75.7) goto は、多用してはいけないとされる。 それは、プログラムの構造がわかりにくくなるからである。 しかし、上のように二重ループから一気に抜け出す際には、 使ってよい。（K&R2 にもそのような例がでている。）
(75.8) N を変えるごとに、何通りの答えがあるかは、 Wikipedia の「エイト・クイーン」に書いてある。 この実習室の linux では、N を 14 にすると、 「うーん、一生懸命がんばっているな」という感じのテンポでの出力になる。 （出力の行数だけを見るには、(74.9) のようにすればよい。）
(75.9) N を 14 にした場合、最初、しばらく出力がないのは、 1 2 ... で始まる 12! 通りの場合はすべて失敗に終わるからである。 より速く答えを求めたいと思ったら、 このような場合を一気に飛ばすことが考えられる。 上で書いたプログラムでは、 「関数 next() で置換をすべて書き出し、 main() の側でそれぞれについて条件 3 （斜め 45 度の線上にある Q の組がないかどうか） を調べる」と分担して仕事をしていた。 そうではなく、両者を合わせて、答えになりえない置換はまとめて飛ばす、 という工夫をすることになる。
(75.10) ※ printf() で使う %d を %x または %X に変えると、 十六進による表示になる。 そうすると、N が 10 から 15 までの場合、 すべての数が一ケタで表示されることになり、 縦に見たとき位置がそろって気持ちがよいかもしれない。