Come generare il set di alimentazione di un set in Scala

Question

Ho un set di elementi di un certo tipo e voglio generare il suo set di alimentazione.

Ho cercato sul Web e non sono riuscito a trovare alcun codice Scala che indirizzi questa specifica attività.

Questo è quello che mi è venuto in mente. Permette di limitare la cardinalità dei set prodotti dal parametro length.

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 
    } 

Questo non include il set vuoto. Per fare ciò è necessario modificare l'ultima riga del metodo semplicemente per res + Set()

Qualche suggerimento su come questo può essere realizzato in uno stile più funzionale?

Answer 1

Si noti che se si dispone di un set S e un altro set T dove T = S ∪ {x} (cioè T è S con un elemento aggiunto) allora la Powerset di T-P(T) - può essere espresso in termini di P(S) e x come segue:

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

cioè, si può definire il powerset ricorsivamente (notate come questo ti dà la dimensione del Powerset gratis - vale a dire l'aggiunta di 1 elemento raddoppia le dimensioni del Powerset). Così, si può fare questo tail-ricorsiva in scala come segue:

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

Poi:

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

Sembra in realtà molto più bello fare lo stesso con un List (cioè un ricorsiva 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]] 

Answer 2

Utilizzare il built-in funzione di 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)) 

Nota, ho imbrogliato e utilizzato un Seq, perché per motivi sconosciuti, combinations è definito su SeqLike. Quindi, con un set, è necessario convertire da/verso 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

Ecco uno dei modi più interessanti di scriverlo:

import scalaz._, Scalaz._ 

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

che funziona come previsto:

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

Vedere ad esempio this discussion thread per una spiegazione di come funziona.

(E come debilski note nei commenti, ListW Pimps anche powerset su List, ma che non è divertente.)

Answer 4

Sembra che nessuno sapeva su di esso di nuovo nel mese di luglio, ma c'è un metodo built-in: 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

Ecco un'altra versione (pigro) ... dal momento che stiamo raccogliendo modi di calcolare la potenza impostata, ho pensato di aggiungo:

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

può essere semplice come:

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

implementazione ricorsiva:

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

Ecco un semplice, soluzione ricorsiva utilizzando una funzione di supporto:

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

quindi la chiamata di

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

darà il risultato

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

Answer 8

Tutte le altre risposte sembravano un po 'complicato, ecco una semplice funzione:

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 
     } 

così

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

produrrà il seguente risultato

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