次へ: 5 必要な回数の評価 上へ: sort1 前へ: 3 簡単な解 (PDF ファイル: sort1-2.pdf)


4 A 列と B 列

次に、初期配列に依存した最適解について考察する。 ここでもしばらくは $M=2$ の場合の方法 A について考えることにする。

3 節同様に最初の列が 1,2,...,$N$ の並びであるとして (前節のかっこのついた数字)、 この配分でどのような列が生成するかを考えることにする。 1,2,...,$N$ の初期配列から全ての順列が生成できれば、 逆に考えれば、全ての順列を整列化できることになる。

今後、この初期配列を 1,2,...,$N$ のように見る方を A 列 と呼び、 元々紙に書かれている数字の並びの方を B 列 と呼ぶこととする。

\begin{displaymath}
\begin{array}{lclc}
\mbox{B 列}: & 4, 2, 1, 3 & \longrightar...
...{A 列}: & 1, 2, 3, 4 & \longrightarrow & 3, 2, 4, 1
\end{array}\end{displaymath}

3 節の例で言えば、A 列の初期配列が 1,2,...,16 で B 列の最終配列が 1,2,...,16 であることになる。

なお、この A 列の最後の並びを $a(1)$,$a(2)$,...,$a(N)$, B 列の初期配列を $b(1)$,$b(2)$,..., $b(N)$ とすると、任意の $j$ に対し

\begin{displaymath}
a(b(j))=j, \hspace{1zw}b(a(j))=j
\end{displaymath}

の関係があることがわかる。これは数学的には、2 つの置換

\begin{displaymath}
\left(\begin{array}{c} i  a(i) \end{array}\right),\hspace{1zw}\left(\begin{array}{c} i  b(i) \end{array}\right)
\end{displaymath}

が逆置換の関係にあることを意味している。


次へ: 5 必要な回数の評価 上へ: sort1 前へ: 3 簡単な解
竹野茂治@新潟工科大学
2006年2月24日