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

Question

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

He buscado en la web y no he podido 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, deberá cambiar la última línea del método simplemente para res + Set()

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

Answer 1

en cuenta que si tiene un conjunto S y otro conjunto T donde T = S ∪ {x} (es decir T es S con un elemento añadido) entonces el powerset de T-P(T) - se puede expresar en términos de P(S) y x como sigue:

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

es decir, se puede definir el powerset recursiva (aviso cómo esto le da el tamaño de la powerset gratis - es decir, la adición de 1-elemento se duplica el tamaño de la powerset). Por lo tanto, usted puede hacer esto de cola de forma recursiva en la 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]] 

continuación:

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 más bonito hacer lo mismo con un List (es decir, un ADT recursiva):

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 2

Utilice el built-in combinations función:

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

Nota, hice trampa y usé un Seq, porque por razones desconocidas, combinations se define en SeqLike. Así que con un conjunto, es necesario 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)) 

Answer 3

He aquí 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 esperaba:

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

Ver por ejemplo this discussion thread para una explicación de cómo funciona.

(Y como debilski notas en los comentarios, ListW proxenetas también powerset en List, pero eso no es divertido.)

Answer 4

Parece que nadie sabía al respecto en julio, pero hay un método integrado: 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 5

Aquí otra versión (perezoso) ... ya que estamos recogiendo formas de computar el conjunto potencia, pensé que me gustaría añadir que:

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

Aquí es una solución simple, recursiva utilizando una función de ayuda:

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

lo 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 8

Todas las otras respuestas parecían un poco complicado, 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 
     } 

por lo

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