- 関数型プログラミング言語Haskell Part29 [転載禁止]©2ch.net
524 ：デフォルトの名無しさん[sage]：2015/09/20(日) 16:52:06.13 ID:KBlLbBcH - >>506
多少は手続き的っぽくない感じで定義してみた
計算量のことなんも考えてないので泥臭さでは全く負けてないけどｗ
置換は[0..(n-1)]に対する任意の置換を[Int]で与えるものとする
import Data.List (nub, nubBy, sort, transpose)
cperms :: [Int] -> [[Int]]
cperms ns = nubBy unique . (map nub) . transpose . (take n)
$ iterate (map (ns!!)) [0..(n-1)]
where n = length ns
unique xs ys = (sort xs) == (sort ys)
-- cperms [0,3,1,2] => [[0], [1,3,2]]
長さnの一般の置換に対して、[0..(n-1)]の各要素をn回、順に置換していって、
軌道に分けて(transpose)、無駄な重複を削除して結果を得る
unique関数では「2つの巡回置換が本質的に等しい」を判定したいんだけど
毎回ソート2回やるより速い方法が絶対あると思う(メモ化するとか)
|
|