subconjuntos - Cómo generar el conjunto de potencia de un conjunto en Scala

conjunto potencia propiedades

Question

Tengo un conjunto de elementos de algún tipo y quiero generar su conjunto de energía.

Busqué en la web y no pude encontrar ningún código de Scala que aborde esta tarea específica.

Esto es lo que se me ocurrió. Le permite restringir la cardinalidad de los conjuntos producidos por el parámetro de longitud.

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
   }

Esto no incluirá el conjunto vacío. Para lograr esto, tendría que cambiar la última línea del método simplemente a res + Set ()

¿Alguna sugerencia de cómo se puede lograr esto en un estilo más funcional?

Answer 1

Aquí está una de las formas más interesantes de escribirlo:

import scalaz._, Scalaz._

def powerSet[A](xs: List[A]) = xs filterM (_ => true :: false :: Nil)

Que funciona como se espera:

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

Vea por ejemplo este hilo de discusión para una explicación de cómo funciona.

(Y como señala Debilski en los comentarios, ListW también proxenetea el conjunto de powerset en List , pero eso no es divertido).

Answer 2

Aquí hay otra versión (perezosa) ... ya que estamos recopilando formas de computar el conjunto de energía, pensé en agregarlo:

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

Answer 3

Aquí hay una solución simple y recursiva que usa una función auxiliar:

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

así que la llamada de

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

dará el resultado

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

Answer 4

Observe que si tiene un conjunto S y otro conjunto T donde T = S ∪ {x} (es decir, T es S con un elemento agregado), entonces el conjunto de potencias de T - P(T) - puede expresarse en términos de P(S) x como sigue:

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

Es decir, puede definir el conjunto de poderes de forma recursiva (observe cómo esto le da el tamaño del conjunto de poderes de forma gratuita, es decir, agregar 1 elemento duplica el tamaño del conjunto de poderes). Entonces, puedes hacer esto en forma recursiva en scala de la siguiente manera:

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

Entonces:

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

En realidad, se ve mucho mejor haciendo lo mismo con una List (es decir, un ADT recursivo):

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

Answer 5

Parece que nadie lo sabía en julio, pero hay un método incorporado: 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)

Answer 6

Puede ser tan simple como:

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

Implementación recursiva:

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

Answer 7

Todas las otras respuestas parecían un poco complicadas, aquí hay una función simple:

    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
      }

asi que

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

producirá el siguiente resultado

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

Answer 8

Utilice la función de combinations incorporada:

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

Tenga en cuenta que hice trampa y usé un Seq , porque por razones desconocidas, las combinations se definen en SeqLike . Así que con un conjunto, necesitas convertir a / desde un 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))