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)
}