如何在Scala中生成一个集合的幂集

Question

我有一组某种类型的项目，想要生成它的幂集。

我在网上搜索了一下，没有找到任何针对这个特定任务的Scala代码。

以下是我提出的解决方案。它允许您通过长度参数限制所生成的集合的基数。

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()。

有任何建议如何以更加函数式的风格完成此操作吗？

- Björn Jacobs

Answer 1

看起来七月份的时候没人知道，但是有一个内置方法：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)

- Luigi Plinge

Answer 2

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

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

也就是说，您可以递归定义幂集（注意，这样可以免费获得幂集的大小 - 即添加一个元素会使幂集的大小翻倍）。因此，您可以在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]]

- oxbow_lakes

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中，但那没有乐趣。)

- Travis Brown

---

我喜欢这个 - 我的问题是，filterM还可以用于什么？ - oxbow_lakes

@oxbow_lakes 例如，您可以进行三向谓词过滤。(x => if ... None/Some(false)/Some(true))。单个None将清除整个输入。但我猜可能会有更高级的用法，使用我从未听说过的奇异单子。 - Debilski

顺便提一下，它是内置的：List(1, 2, 3).powerset. :) - Debilski

@oxbow_lakes: let doYouLike it = fmap (== "y") $ putStr ("do you like " ++ show it ++ " (y/n)? ") >> getLine in filterM doYouLike ["scala", "haskell"] - Travis Brown

filterM和类似函数对于M=[a]State[X, a]非常有用。例如，你可以使用以下代码过滤重复项：https://gist.github.com/3157243 - retronym

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))

- Luigi Plinge

---

但是使用set，它是否保持词典顺序集合？ - Shankar Shastri

Answer 5

可以非常简单，比如：

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = 
  xs.foldLeft(Seq(Seq[A]())) {(sets, set) => sets ++ sets.map(_ :+ set)}

递归实现：

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = {
  def go(xsRemaining: Seq[A], sets: Seq[Seq[A]]): Seq[Seq[A]] = xsRemaining match {
    case Nil => sets
    case y :: ys => go(ys, sets ++ sets.map(_ :+ y))
  }

  go(xs, Seq[Seq[A]](Seq[A]()))
}

- Cristian

---

虽然这段代码可能回答了问题，但最好包含一些上下文，解释它的工作原理以及何时使用它。仅有代码的答案从长远来看并不有用。 - Benjamin W.

对于foldLeft的实现，我给予赞扬。我特别在寻找这个实现。正如早期评论者所说，解释会更好。 - BrutalSimplicity

Answer 6

其他答案似乎有点复杂，这里是一个简单的函数：

    def powerSet (l:List[_]) : List[List[Any]] =
      l match {
       case Nil => List(List())
       case x::xs =>
         var a = powerSet(xs)
         a.map(n => n:::List(x)):::a
      }

so

    powerSet(List('a','b','c'))

将会产生以下结果

    res0: List[List[Any]] = List(List(c, b, a), List(b, a), List(c, a), List(a), List(c, b), List(b), List(c), List())

- yassine mhedhbi

Answer 7

这里是另一种（懒惰的）版本...由于我们正在收集计算幂集的方法，所以我想添加它：

def powerset[A](s: Seq[A]) =
  Iterator.range(0, 1 << s.length).map(i =>
    Iterator.range(0, s.length).withFilter(j =>
      (i >> j) % 2 == 1
    ).map(s)
  )

- borice

Answer 8

这是一个使用辅助函数的简单递归解决方案：

def concatElemToList[A](a: A, list: List[A]): List[Any] = (a,list) match {
    case (x, Nil)                 => List(List(x))
    case (x, ((h:List[_]) :: t))  => (x :: h) :: concatElemToList(x, t)
    case (x, (h::t))              => List(x, h) :: concatElemToList(x, t)
}

def powerSetRec[A] (a: List[A]): List[Any] = a match {
    case Nil    => List()
    case (h::t) => powerSetRec(t) ++ concatElemToList(h, powerSetRec (t))
}

所以调用

powerSetRec(List("a", "b", "c"))

将返回结果

List(List(c), List(b, c), List(b), List(a, c), List(a, b, c), List(a, b), List(a))

- Andra Pravai

---

结果中缺少空集。 - Cristian