Как сгенерировать набор мощности набора в Scala

У меня есть набор элементов некоторого типа и вы хотите сгенерировать его набор мощности.

Я искал в Интернете и не мог найти код 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()

Любые предложения, как это можно сделать в более функциональном стиле?

Ответ 1

Обратите внимание, что если у вас есть набор S и другой набор T, где T = S ∪ {x} (т.е. T есть S с добавленным элементом), тогда силовой набор T - P(T) - может выражаются через P(S) и x следующим образом:

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

То есть, вы можете определить рекурсивно синтаксис (обратите внимание на то, как это дает вам размер бесплатной загрузки), т.е. добавление 1-элемента удваивает размер силового набора). Таким образом, вы можете сделать это хвостовым рекурсивом в 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]]

Ответ 2

Похоже, никто не знал об этом еще в июле, но есть встроенный метод: 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)

Ответ 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()

См., например, эту дискуссионную тему для объяснения того, как она работает.

(И как отмечает дебильский в комментариях, ListW также сутенеры powerset на List, но это не забавно.)

Ответ 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. Поэтому с набором вам нужно преобразовать в/из a 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))

Ответ 5

Здесь другая (ленивая) версия... поскольку мы собираем способы вычисления мощности, я думал, что добавлю ее:

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

Ответ 6

Может быть так же просто, как:

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

Ответ 7

Здесь простое рекурсивное решение с использованием вспомогательной функции:

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

Ответ 8

Все остальные ответы казались немного сложными, вот простая функция:

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