问题:
给定一个 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
(是的,我选择了相同的名称),它返回迭代器。我也想过这个,但我还不知道如何懒惰地设计它。
最佳答案
不确定这是否足以满足您的目的,但这是最简单的方法。
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))
}
关于scala - 元素组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25099802/