あるタイプのアイテムのセットがあり、そのパワーセットを生成したいと思います。
Webを検索しましたが、この特定のタスクに対応する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（）に変更する必要があります。
これをより機能的なスタイルで実現する方法について何か提案はありますか？
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)
セットSと別のセットTがある場合T = S ∪ {x}（つまり、1つの要素が追加されている場合）、---のべき集合Tは次の ように表すことができます。STP(T)P(S)x
P(T) = P(S) ∪ { p ∪ {x} | p ∈ P(S) }
つまり、べき集合を再帰的に定義できます（これにより、べき集合のサイズが無料で得られることに注意してください。つまり、1要素を追加するとべき集合のサイズが2倍になります）。したがって、次のように、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]]
これを書くためのより興味深い方法の1つは次のとおりです。
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が、それは楽しいことではありません。）
組み込み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))
次のように単純にすることができます。
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]()))
}
他のすべての答えは少し複雑に見えました、ここに単純な関数があります：
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
}
それで
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())
これが別の（怠惰な）バージョンです...べき集合を計算する方法を収集しているので、私はそれを追加すると思いました：
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)
)
ヘルパー関数を使用した単純な再帰的ソリューションは次のとおりです。
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))