Set[T]から取りうるすべての組み合わせを生成するにはsubsets

タイトルの通り。

scala> Set(1,2,3)
val res0: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> res0.subsets().toList
val res1: List[scala.collection.immutable.Set[Int]] = List(Set(), Set(1), Set(2), Set(3), Set(1, 2), Set(1, 3), Set(2, 3), Set(1, 2, 3))

引数にInt値を取ることができ、その場合は要素数が引数の値になるSetのみを含むことになる

scala> res0.subsets(2).toList
val res2: List[scala.collection.immutable.Set[Int]] = List(Set(1, 2), Set(1, 3), Set(2, 3))

アルゴリズム本で N個の自然数a0~aN-1と任意の自然数Wが与えられたとき、和がWになる組み合わせが存在することを判定 みたいな例題があったときにこりゃ便利だなと思った。

こんな感じ

def hasCombinationSumEqual(set: Set[Int])(sumEqual: Int): Boolean = set.subsets.exists(c => c.size > 1 && c.sum == sumEqual)

本としての意図はそれを実装しろということなんだろうけど。。。

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)

なお似たものに subsetOf(that: Set[A]) があるが全く別物で、 thisが引数に与えた that: Set[A] の部分集合であることを検証するものである。

// Set[T].apply(value: T)はexists(value: T)のエイリアスなのでthat.applyはthat.existsを意味する
def subsetOf(that: Set[A]): Boolean = this.forall(that)