// See http://www.itmn.biz/
//      > ３×３魔方陣　問題
//     http://www.ne.jp/asahi/suzuki/hp/houjin3.htm
//      > 魔方陣
//     http://www.grogono.com/magic/makeyourown4.php
//     > Make Your Own 4x4 Magic Square
//     http://quasistoic.org/fun/magicsquare/
//       > 4x4 Magic Square Solver
//     http://quasistoic.org/ts/archives/2006/08/13/magic-square-solver/
//        > magic square generator

package perm

object Perms {

    // ls の順列全体 の n 番目 (n = [0 ... (n!-1) の範囲]) のものを得る
    def perm_nth[A](ls:List[A], n:BigInt):List[A] = {
        ls.length match {
            case 0 => List[A]()
            case 1 => ls
            case len => {
                    val f = Fact.factMem(len - 1)
                    val v = ls.apply((n / f).intValue)
                    v :: perm_nth(ls.filter( _ != v ), n % f)
                }
        }
    }

    // List[A] の順列全体を得る
    def perms[A](l:List[A]):List[List[A]] = {
        // ある要素をリストに挿入した結果のリスト
        l match {
            case Nil => List(Nil)
            case (x::xs) => flatList( perms(xs).map(insertItem(x,_)))
        }
    }
    private def insertItem[A](h:A, l:List[A]):List[List[A]] = {
        // ある要素をリストに挿入した結果のリスト
        l match {
            case Nil => List(List(h))
            case x::xs => (h::x::xs) :: insertItem(h,xs).map(x :: _)
        }
    }
    // ネストしたリストを１階層だけバラす。
    private def flatList[A](xss:List[List[A]]):List[A] = xss.reduceLeft((xs, x) => xs ::: x)
}
