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

问题描述

我有一些类型的物品套装，想生成它的能量套装.

I have a Set of items of some type and want to generate its power set.

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

I searched the web and couldn't find any Scala code that adresses this specific task.

这是我想出的.它允许您限制length参数产生的集合的基数.

This is what I came up with. It allows you to restrict the cardinality of the sets produced by the length parameter.

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

This will not include the empty set. To accomplish this you would have to change the last line of the method simply to res + Set()

有人建议如何以更实用的方式完成此工作吗?

Any suggestions how this can be accomplished in a more functional style?

推荐答案

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

Notice that if you have a set S and another set T where T = S ∪ {x} (i.e. T is S with one element added) then the powerset of T - P(T) - can be expressed in terms of P(S) and x as follows:

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

也就是说，您可以递归定义电源集(请注意，这是如何免费为您提供电源集大小的-即添加1元素会使电源集大小增加一倍).因此，您可以按以下步骤在scala中以递归方式执行此操作:

That is, you can define the powerset recursively (notice how this gives you the size of the powerset for free - i.e. adding 1-element doubles the size of the powerset). So, you can do this tail-recursively in scala as follows:

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)执行此操作实际上看起来要好得多:

It actually looks much nicer doing the same with a List (i.e. a recursive 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]]

这篇关于如何在Scala中生成集合的幂集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！