問題
1からまでの数で個からなる重複しない数の順列を作り出す算法として，下記のものを考えた．ただし，は順列を表し，算法の開始の時は数を含まない（は空であるという）とする．算法の終了時には結果として順列を得るものとする．
算法［以下(a)，(b)，(c)，の順に行う］
(a) を空とし，とする．
(b) 1からまでの数からデタラメに数を選ぶ．
(c) が順列に入っているならば，の直後にを入れ，そうでないならば，をの先頭に入れる．
(d) を1増やす．
(e) ならば，(b)へもどる．ならば，終了する．
(1) ，の場合で(b)において選ばれた数は順に4，3，6，3，2，5であった．その結果として得られる順列はどのような順列か．
(2) ，の場合で結果として得られた順列が827593であった．(b)で選ばれた数の列は何であったか．
(3) 算法の結果として得られた順列から(b)において選ばれた数の列を復元する算法を記述せよ．
方針
算法をそのまま追う問題である。(1)では から まで、選ばれた が現在の順列に含まれるかを毎回判定して挿入位置を決める。(2)では逆向きに、最大の から順に取り除く。 が順列中にあればその直前の数が選ばれた 、 がなければ先頭に入った数そのものが である。一般の復元算法もこの逆操作を記述すればよい。
解答
(1)
、 なので、最初は である。選ばれた は順に である。
順に操作する。はじめ は空である。 、 のとき、4は に入っていないので4を先頭に入れる。 、 のとき、3は入っていないので である。、 のとき、6は入っていないので である。、 のとき、3は に入っているので、3の直後に8を入れて となる。、 のとき、2は入っていないので である。最後に 、 のとき、5は入っていないので となる。したがって得られる順列は である。
(2)
逆向きに考える。結果が である。最後に処理された は10であるが、10は に含まれていない。したがって最後の操作では、選ばれた が先頭に入れられて消えた形であり、最後の は先頭の8である。8を取り除いて となる。
次に を戻す。9は順列中にあり、その直前は5である。よってこの段階の は5であり、9を取り除いて となる。次に は含まれていないので、先頭の2がその段階の であり、2を取り除いて となる。次に は含まれているが、先頭にあるので、7は「 の直後に入った」のではなく、 自身が先頭に入った場合である。したがってこの段階の は7であり、7を取り除く。 次に は含まれていないので、先頭の5が であり、5を取り除く。 最後に は含まれていないので、先頭の3が である。
以上は後ろから復元した値なので、元の順に並べると である。
(3)
結果として得られた順列を とする。復元は次の手順で行えばよい。 の順に処理する。各段階で、もし が現在の の中にあり、しかも直前に数があるなら、その直前の数をその段階の として記録し、 を から取り除く。もし が に含まれない、または が先頭にあるなら、現在の の先頭の数をその段階の として記録し、その先頭の数を から取り除く。
この操作で得られる の列は後ろからの列なので、最後に逆順に並べれば、(b)で選ばれた数の列が復元される。