整数分割

Scala 30分プログラム

30分プログラム、その728。wikipedia:整数分割をやってみた。

"並び順を変えても同じ整数分割とみなす"という条件がわりときつくて、それを満たす引数を一個増やしています。

使い方

scala> partition(5)
res9: Seq[List[Int]] = RangeG(List(1, 1, 1, 1, 1),
                              List(2, 1, 1, 1),
                              List(2, 2, 1),
                              List(3, 1, 1),
                              List(3, 2),
                              List(4, 1),
                              List(5))

ソースコード

def int_partition(n : Int, max : Int) : Seq[List[Int]] = {
  if(n == 0)
    List(List())
  else
    (1 to (max min n)).toList.flatMap{ i =>
      int_partition(n - i, i).map(i::_)
    }
}

def partition(n : Int) = int_partition(n,n)

参考