Scalaで順列と組合せ
List同士の結合は避けたのでそこそこ効率は良い・・と思う。
Rubyに入った重複版も書いてみた。
def permutation[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = { def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] = if (n == 0) Stream(ls) else { def g(s: Stream[A], s2: Stream[A]): Stream[Stream[A]] = if (s.isEmpty) Stream.Empty else (s #::: s2) #:: g(s.tail, s.head #:: s2) g(rest, Stream.empty).flatMap(s => f(s.head :: ls, s.tail, n - 1)) } f(Nil, trv1.toStream, n) } def combination[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = { def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] = if (n == 0) Stream(ls) else if (rest.isEmpty) Stream.empty else f(rest.head :: ls, rest.tail, n - 1) #::: f(ls, rest.tail, n) f(Nil, trv1.toStream, n) } def repeatedPermutation[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = if (trv1.isEmpty) Stream.empty else { def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] = if (n == 0) Stream(ls) else rest.flatMap(v => f(v :: ls, rest, n - 1)) f(Nil, trv1.toStream, n) } def repeatedCombination[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = { def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] = if (n == 0) Stream(ls) else if (rest.isEmpty) Stream.empty else f(rest.head :: ls, rest, n - 1) #::: f(ls, rest.tail, n) f(Nil, trv1.toStream, n) }