如何在Scala中生成一组集的功率集

发布时间：2020-12-16 09:30:50 所属栏目：安全来源：网络整理

导读：我有一些类型的项目，并希望生成其功率集。我在网上搜索，找不到适合这个特定任务的任何Scala代码。这是我想出来的。它允许您限制由length参数生成的集合的基数。 def power[T](set: Set[T],length: Int) = { var res = Set[Set[T]]() res ++= set.map(Set

我有一些类型的项目，并希望生成其功率集。

我在网上搜索，找不到适合这个特定任务的任何Scala代码。

这是我想出来的。它允许您限制由length参数生成的集合的基数。

def power[T](set: Set[T],length: Int) = {
   var res = Set[Set[T]]()
   res ++= set.map(Set(_))

   for (i <- 1 until length)
      res = res.map(x => set.map(x + _)).flatten

   res
   }

这不包括空集。要完成这个，你将不得不将该方法的最后一行改为res Set()

有什么建议，可以如何实现更有功能的风格？

解决方法

注意，如果你有一个集合S和另一个集合T，其中T = S∪{x}(即，T是具有一个元素的S，那么T-P(T)的幂组可以用P(S )和x如下：

P(T) = P(S) ∪ { p ∪ {x} | p ∈ P(S) }

也就是说，你可以递归地定义poweret(注意这是如何给你免费的poweret的大小 – 即添加1元素将poweret的大小加倍)。因此，您可以在scala中以递归方式执行以下操作：

scala> def power[A](t: Set[A]): Set[Set[A]] = {
   |     @annotation.tailrec 
   |     def pwr(t: Set[A],ps: Set[Set[A]]): Set[Set[A]] =
   |       if (t.isEmpty) ps
   |       else pwr(t.tail,ps ++ (ps map (_ + t.head)))
   |
   |     pwr(t,Set(Set.empty[A])) //Powerset of ? is {?}
   |   }
power: [A](t: Set[A])Set[Set[A]]

然后：

scala> power(Set(1,2,3))
res2: Set[Set[Int]] = Set(Set(1,3),Set(2,Set(),Set(3),Set(2),Set(1),Set(1,2))

它实际上看起来更好做同样的List(即递归ADT)：

scala> def power[A](s: List[A]): List[List[A]] = {
   |     @annotation.tailrec 
   |     def pwr(s: List[A],acc: List[List[A]]): List[List[A]] = s match {
   |       case Nil     => acc 
   |       case a :: as => pwr(as,acc ::: (acc map (a :: _)))
   |     }
   |     pwr(s,Nil :: Nil)
   |   }
power: [A](s: List[A])List[List[A]]

（编辑：李大同）

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