数を並びかえる(2)

参考文献 : プログラミング Clojure 第2版、(Stuart Halloway and Aaron Bedra 著、川合史朗 訳、オーム社)

数を並びかえる(1)

置換の偶奇を決めるために転倒数を求めたい。

  1. 最初の要素をとる。
  2. 最初の要素より小さな要素を数える。
  3. 最初の要素を切り落して 1 に戻る。

2 で求めた数を合計したものが転倒数。

こういうのは再帰で書くのが自然と思われる :

(defn inversion-number [permutation]
  (loop [coll permutation result 0]
    (if (empty? coll) 
      result
      (let [f (first coll) r (rest coll)]
        (recur r (+ result (count (filter #(> f %) r))))))))
        
(inversion-number [4 3 2 1])
=>
6

置換の偶奇を定める :

(defn even-permutation? [permutation]
  (even? (inversion-number permutation)))

(defn odd-permutation? [permutation]
  (not (even-permutation? permutation)))
  
(map even-permutation? (permutation [1 2 3]))
=>
(true false false true true false)

\(S_{n}\) に対して使うなら

(map #(even-permutation? (%)) S3)
=>
(true false false true true false)

のようにする。

\(S_{n}\) の逆元 :

(defn inverse [f]
  (make-fn (mapv #(inc (.indexOf (f) %)) (range1-n (count (f))))))

(f) とすることで f が保持している置換が得られることに注意。 \( (f) = [f(1),…,f(n)]\) の逆の対応をつけている。

ところで .indexOfjava の関数なので (fn? .indexOf) はエラーとなる。

使ってみる :

(S3 3)
=>
#function[user/make-fn/fn--49822]

(*1)
=>
[2 3 1]

(inverse (S3 3))
=>
#function[user/make-fn/fn--49822]

(*1)
=>
[3 1 2]

(S3 3)S3 の 4番目の要素。リストだと nth でアクセスしなければならないがベクトルだとインデックスでアクセスできる。それで make-fns では mapv を使ったのです。

\(S_{n}\) は関数の集合なので #function のリストが返ってしまう。置換としてみたほうが見やすいので

(defn as-permutation [S] (map #(%) S))

とする。(最初は #((%)) としてみたがエラーとなってしまった。)

(as-permutation S3)
=>
([1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1])

\(S_{n}\) の部分集合が等しいこと :

(defn sg= [X Y]
  (= (set (as-permutation X))
     (set (as-permutation Y))))

\( S_3 = S_{3}^{-1} \) を確認する。

(sg= S3 (map inverse S3))
=>
true

\(S_{n}\) に積を入れたい :

(defn product [& fns]
  (make-fn (mapv (apply comp fns) (range1-n (count ((first fns)))))))

comp は合成(compose)。

使ってみる :

((product (S3 2) (S3 3) (S3 4)))
=>
[2 1 3]

((product (S3 5) (inverse (S3 5)))) ; x x^{-1} = id
=>
[1 2 3] 

続く。

広告を非表示にする