如何在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

看起来在7月没有人知道它,但有一个内置的方法:subsets.

scala> Set(1,2,3).subsets foreach println
Set()
Set(1)
Set(2)
Set(3)
Set(1, 2)
Set(1, 3)
Set(2, 3)
Set(1, 2, 3)

Answer 2

请注意,如果您有一组S,另一组T在那里T = S ? {x}(即T是S一个加入的元素),那么的幂T- P(T)-可在来表示P(S),并x如下:

P(T) = P(S) ? { p ? {x} | p ? P(S) }

也就是说,你可以递归地定义powerset(请注意它如何免费提供powerset的大小 - 即添加1个元素使powerset的大小加倍).因此,您可以在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))

它实际上看起来更好用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]]

Answer 3

这是编写它的一种更有趣的方法:

import scalaz._, Scalaz._

def powerSet[A](xs: List[A]) = xs filterM (_ => true :: false :: Nil)

哪个按预期工作:

scala> powerSet(List(1, 2, 3)) foreach println
List(1, 2, 3)
List(1, 2)
List(1, 3)
List(1)
List(2, 3)
List(2)
List(3)
List()

请参阅此讨论主题以获取其工作原理的说明.

(正如在评论debilski笔记,ListW也皮条客powerset到List,但是这不好玩.)

Answer 4

使用内置combinations功能:

val xs = Seq(1,2,3)
(0 to xs.size) flatMap xs.combinations

// Vector(List(), List(1), List(2), List(3), List(1, 2), List(1, 3), List(2, 3),
// List(1, 2, 3))

注意,我作弊并使用了一个Seq,因为原因不明,combinations是定义的SeqLike.所以有了一个集合,你需要转换为/来自Seq:

val xs = Set(1,2,3)
(0 to xs.size).flatMap(xs.toSeq.combinations).map(_.toSet).toSet

//Set(Set(1, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), 
//Set(1, 2))