scala - 如何在Scala中生成集合的幂集

Question

我有一些类型的项目集，想要生成其功率集。

我在网上搜索，找不到适合此特定任务的任何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()

有什么建议可以以更实用的方式实现吗？

Answer 1

请注意，如果您有一个S设置和另一个T设置(其中T = S ∪ {x}是T并添加了一个元素)，则S的幂集-T-可以用P(T)和P(S)表示，如下所示:

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

也就是说，您可以递归定义功率集(请注意，这是如何免费为您提供功率集大小的-即添加1元素会使功率集大小增加一倍)。因此，您可以按以下步骤在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, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), Set(1, 2))

实际上，使用x(即递归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]]