scala - 元素组合

Question

问题:

给定一个 Seq seq和一个 Int n .

我基本上想要元素的所有组合 高达 大小 n.安排事项 , 意思是例如[1,2] 与 [2,1] 不同。

def combinations[T](seq: Seq[T], size: Int) = ...

示例:

combinations(List(1,2,3), 0) 
//Seq(Seq())

combinations(List(1,2,3), 1)
//Seq(Seq(), Seq(1), Seq(2), Seq(3))

combinations(List(1,2,3), 2) 
//Seq(Seq(), Seq(1), Seq(2), Seq(3), Seq(1,2), Seq(2,1), Seq(1,3), Seq(3,1),
//Seq(2,3), Seq(3,2))

...

到目前为止我所拥有的:

def combinations[T](seq: Seq[T], size: Int) = {
 @tailrec
  def inner(seq: Seq[T], soFar: Seq[Seq[T]]): Seq[Seq[T]] = seq match {
    case head +: tail => inner(tail, soFar ++ {
      val insertList = Seq(head)
      for {
        comb <- soFar
        if comb.size < size
        index <- 0 to comb.size
      } yield comb.patch(index, insertList, 0)
    })
    case _ => soFar
  }

  inner(seq, IndexedSeq(IndexedSeq.empty))
}

你对这个问题的处理方法是什么？此方法将被称为 很多因此它应该是最有效的。

库中有类似 subsets 的方法或 combinations (是的，我选择了相同的名称)，它返回迭代器。我也想过这个，但我还不知道如何懒惰地设计它。

Answer 1

不确定这是否足以满足您的目的，但这是最简单的方法。

def combinations[T](seq: Seq[T], size: Int) : Seq[Seq[T]] = {
  (1 to size).flatMap(i => seq.combinations(i).flatMap(_.permutations))
}

编辑:
为了使它变得懒惰，您可以使用 View

def combinations[T](seq: Seq[T], size: Int) : Iterable[Seq[T]] = {
  (1 to size).view.flatMap(i => seq.combinations(i).flatMap(_.permutations))
}