scala – 元素的组合

发布时间：2020-12-16 18:55:27 所属栏目：安全来源：网络整理

导读：问题：给定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,1)//Seq(Seq(),Seq(1),S

问题：

给定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,1)
//Seq(Seq(),Seq(1),Seq(2),Seq(3))

combinations(List(1,2) 
//Seq(Seq(),Seq(3),Seq(1,2),Seq(2,1),Seq(3,//Seq(2,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))
}

你对这个问题有什么看法？这种方法将被大量调用,因此应该最有效.

库中有一些方法,比如子集或组合(我选择了相同的名称),它们返回迭代器.我也考虑过这一点,但我还不知道如何设计这个懒惰.

解决方法

不确定这是否足够有效,但这是最简单的方法.

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

编辑：
为了使它变得懒惰你可以使用视图

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!