2016年7月7日

日記

置換に関するコードをあれこれ書いてるんだが、整数から整数への写像として定義する「アクティブ」な定義と、ある適当な型(型パラメータ)を指定してその型から同じ型への写像として定義する「パッシブ」な定義の2通りでそれなりに API が書けてきた。 で、次に n 個から r 個取り出して並べる部分置換(部分順列と言った方がいいのか)も同じようにコーディングしようとしたのだが、思いの外うまくいきそうにないw

部分順列を整数から整数への写像として定義しようとすると、置換と違って定義域と値域はことなる集合になるのは仕方ない。 5個のもの  { x_0,\,x_1,\,\cdots x_4 } から3個選ぶとき、置換の場合と同じように順序付けられた列

  { \displaystyle\begin{align*}
  (x_0,\,x_1,\,x_2)
\end{align*}}

に部分順列  { \sigma } を施して、例えば

  { \displaystyle\begin{align*}
  (x_{\sigma(0)},\,x_{\sigma(1)},\,x_{\sigma(2)})
    = (x_4,\,x_0,\,x_3)
\end{align*}}

みたいになるように定義するのが写像としての置換の定義に対するアナロジーだと思う。 この場合、部分順列  { \sigma } { \{0,\,1,\,2\} } から  { \{0,\,1,\,\cdots,4\} } への単射ってことになる。 でもこれだと、さらに3個のものから2個のものを取り出して並べる部分順列を作用させたいときに、定義域に含まれない4などを写せないといけなくなる。 まぁ、置換の場合の「パッシブ」な定義みたいなことをやればそういう部分順列も定義できるけど、各部分順列によって写された列それぞれに別の定義域を持つ部分順列を定義していかないといけなくなるので、全く美しくない。

置換  { \sigma } に対して、 { \sigma(0) = 1 } を「0の位置にあるものを1の位置に移す」という定義に基づいた置換と解釈した場合、部分置換もほとんど同じように定義できてしまうんだけど・・・

ツイート (ツイート数 63)