स्कैला

Question

में सेट के पावर सेट को कैसे उत्पन्न करें मेरे पास कुछ प्रकार के आइटम हैं और इसके पावर सेट जेनरेट करना चाहते हैं।

मैंने वेब की खोज की और मुझे कोई विशिष्ट स्कैला कोड नहीं मिला जो इस विशिष्ट कार्य को संबोधित करता है।

यही वह है जो मैं आया था। यह आपको लंबाई पैरामीटर द्वारा उत्पादित सेट की कार्डिनालिटी को प्रतिबंधित करने की अनुमति देता है।

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 
    } 

इसमें खाली सेट शामिल नहीं होगा। इसे पूरा करने के लिए आपको विधि की अंतिम पंक्ति को बस सेट करना होगा + सेट()

कोई सुझाव यह एक और कार्यात्मक शैली में कैसे पूरा किया जा सकता है?

Answer 1

सूचना आप एक सेट S है और यदि एक और सेट है कि T जहां T = S ∪ {x} (एक तत्व के साथ जोड़ा यानी TS है) तो T की Powerset - P(T) - P(S) के मामले में x के रूप में व्यक्त किया जा सकता है इस प्रकार है:

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

है, तो आप Powerset रिकर्सिवली (- यानी 1-तत्व जोड़ Powerset का आकार दोगुना हो जाता है नोटिस कि यह कैसे आप मुक्त करने के लिए Powerset के आकार देता है) को परिभाषित कर सकते हैं। तब

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 के साथ एक ही लग रहा है (यानी एक पुनरावर्ती एडीटी):

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

का प्रयोग करें निर्मित 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 का उपयोग किया, क्योंकि अज्ञात कारणों से combinationsSeqLike पर परिभाषित किया गया है। एक सेट के साथ तो, आप करने के लिए/परिवर्तित करने के लिए एक 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

यहाँ और अधिक दिलचस्प तरीके यह लिखने के लिए में से एक है:

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

उदाहरण के लिए this discussion thread देखें कि यह कैसे काम करता है इसकी व्याख्या के लिए।

(और टिप्पणियों में debilski नोटों के रूप में, ListW भी powersetList पर pimps, लेकिन है कि कोई मज़ा है।)

Answer 4

ऐसा लगता है कि कोई इसके बारे में जुलाई में वापस जानता था, लेकिन वहाँ एक अंतर्निहित विधि है: 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

यहाँ एक और (आलसी) संस्करण है ... क्योंकि हम बिजली सेट की गणना के तरीके एकत्र कर रहे हैं मैंने सोचा कि मैं यह जोड़ेंगे:

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

में सरल किया जा सकता है के रूप में:

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

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

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