स्कैला

Question

में पुनरावृत्ति के साथ लिस्टिंग संयोजन स्कैला का थोड़ा सा सीखने और इस समस्या में भाग गया। मुझे here दोहराए बिना सभी संयोजनों का समाधान मिला और मैं इसके पीछे विचार समझता हूं लेकिन कुछ वाक्यविन्यास मुझे गड़बड़ कर रहा है। मुझे यह भी नहीं लगता कि समाधान पुनरावृत्ति के मामले में उपयुक्त है। मैं सोच रहा था कि अगर कोई ऐसा कोड सुझा सकता है जिसे मैं काम कर सकता हूं। मेरे पास संयोजक पर बहुत सारी सामग्री है और समस्या और पुनरावृत्तियों के समाधान को समझते हैं, मैं बस इसे करने के स्कैला-वाई तरीके की तलाश में हूं।

धन्यवाद

Answer 1

अब मैं आपका प्रश्न समझता हूं। मुझे लगता है कि सबसे आसान तरीका प्राप्त करने के लिए आप क्या चाहते हैं निम्न करने के लिए है:

def mycomb[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l; 
       sl <- mycomb(n-1, l dropWhile { _ != el })) 
       yield el :: sl 
} 

def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.removeDuplicates) 

comb विधि सिर्फ कॉल इनपुट सूची से हटा दिया डुप्लिकेट के साथ mycomb। डुप्लिकेट को हटाने का मतलब है कि बाद में परीक्षण करना आसान होता है कि दो तत्व 'समान' हैं या नहीं।आपके mycomb विधि में किए गए एकमात्र परिवर्तन यह है कि जब विधि को रिकर्सिवली कहा जा रहा है, तो मैं सूची में el से पहले दिखाई देने वाले तत्वों को बंद कर देता हूं। यह आउटपुट में डुप्लिकेट होने से रोकने के लिए है।

> comb(3, List(1,2,3)) 
> List[List[Int]] = List(
    List(1, 1, 1), List(1, 1, 2), List(1, 1, 3), List(1, 2, 2), 
    List(1, 2, 3), List(1, 3, 3), List(2, 2, 2), List(2, 2, 3), 
    List(2, 3, 3), List(3, 3, 3)) 

> comb(6, List(1,2,1,2,1,2,1,2,1,2)) 
> List[List[Int]] = List(
    List(1, 1, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 2), List(1, 1, 1, 1, 2, 2), 
    List(1, 1, 1, 2, 2, 2), List(1, 1, 2, 2, 2, 2), List(1, 2, 2, 2, 2, 2), 
    List(2, 2, 2, 2, 2, 2)) 

Answer 2

सवाल जवाब में से एक में rephrased था - मुझे आशा है कि सवाल ही भी संपादित हो जाता है। किसी और ने उचित सवाल का जवाब दिया। यदि कोई इसे उपयोगी पाता है तो मैं उस कोड को नीचे छोड़ दूंगा।

वह समाधान वास्तव में नरक के रूप में उलझन में है। पुनरावृत्ति के बिना "संयोजन" को क्रमपरिवर्तन कहा जाता है। यह इस तरह से जा सकते हैं: के रूप में एक और जवाब में सुझाव दिया इनपुट सूची, अद्वितीय तत्व होते हैं की गारंटी नहीं है

def perm[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l; 
        sl <- perm(n-1, l filter (_ != el))) 
       yield el :: sl 
    } 

हैं, तो यह थोड़ा और अधिक कठिन हो सकता है। फिल्टर के बजाय, जो सभी तत्वों को हटा देता है, हमें केवल पहले को हटाने की आवश्यकता है।

def perm[T](n: Int, l: List[T]): List[List[T]] = { 
    def perm1[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
     case 0 => List(List()) 
     case _ => for(el <- l; 
        (hd, tl) = l span (_ != el); 
        sl <- perm(n-1, hd ::: tl.tail)) 
       yield el :: sl 
    } 
    perm1(n, l).removeDuplicates 
} 

बस कुछ स्पष्टीकरण। इसके लिए, हम सूची के प्रत्येक तत्व को लेते हैं, और इसके द्वारा बनाई गई सूची को चयनित तत्व के अलावा सूची के सभी तत्वों के क्रमपरिवर्तन के बाद।

उदाहरण के लिए, यदि हम सूची (1,2,3) लेते हैं, तो हम 1 और परम (सूची (2,3)), 2 और परम (सूची (1,3)) द्वारा बनाई गई सूचियां लिखेंगे और 3 और परम (सूची (1,2))।

चूंकि हम मनमाने ढंग से आकार के क्रमपरिवर्तन कर रहे हैं, इसलिए हम ट्रैक करते हैं कि प्रत्येक उप-गणना कितनी देर तक हो सकती है। यदि उप-क्रमशः आकार 0 है, तो यह महत्वपूर्ण है कि हम एक खाली सूची वाली एक सूची वापस कर दें। ध्यान दें कि यह एक खाली सूची नहीं है! अगर हम 0 के मामले में नील लौटाते हैं, तो कॉलिंग परम में एसएल के लिए कोई तत्व नहीं होगा, और पूरे "के लिए" नील पैदा करेगा। इस तरह, एसएल को निल सौंपा जाएगा, और हम एक सूची एल :: नील लिखेंगे, सूची (एल) उपज।

मैं मूल समस्या के बारे में सोच रहा था, हालांकि, और मैं संदर्भ के लिए यहां अपना समाधान पोस्ट करूंगा। यदि आपके पास इनपुट में डुप्लिकेट तत्वों के परिणामस्वरूप उत्तर में डुप्लीकेट तत्व नहीं हैं, तो नीचे दिखाए गए अनुसार हटाएं डुप्लिकेट जोड़ें।

def comb[T](n: Int, l: List[T]): List[List[T]] = 
n match { 
    case 0 => List(List()) 
    case _ => for(i <- (0 to (l.size - n)).toList; 
       l1 = l.drop(i); 
       sl <- comb(n-1, l1.tail)) 
      yield l1.head :: sl 
} 

यह थोड़ा बदसूरत है, मुझे पता है। मुझे सूची में सूची ("से" द्वारा लौटाई गई) को बदलने के लिए लिस्ट का उपयोग करना होगा, ताकि "इसके लिए" स्वयं एक सूची लौटाए। मैं "एल 1" से दूर हो सकता था, लेकिन मुझे लगता है कि यह और स्पष्ट करता है कि मैं क्या कर रहा हूं।चूंकि कोई फिल्टर यहाँ है, यह डुप्लिकेट को निकालने के संशोधित किया जाता है बहुत आसान है:

def comb[T](n: Int, l: List[T]): List[List[T]] = { 
    def comb1[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
     case 0 => List(List()) 
     case _ => for(i <- (0 to (l.size - n)).toList; 
        l1 = l.drop(i); 
        sl <- comb(n-1, l1.tail)) 
       yield l1.head :: sl 
    } 
    comb1(n, l).removeDuplicates 
} 

Answer 3

डैनियल - मुझे यकीन है कि एलेक्स डुप्लिकेट से क्या मतलब नहीं कर रहा हूँ, यह हो सकता है कि निम्नलिखित ज्यादा उपयुक्त जवाब प्रदान करता है:

def perm[T](n: Int, l: List[T]): List[List[T]] = 
    n match { 
    case 0 => List(List()) 
    case _ => for(el <- l.removeDuplicates; 
       sl <- perm(n-1, l.slice(0, l.findIndexOf {_ == el}) ++ l.slice(1 + l.findIndexOf {_ == el}, l.size))) 
      yield el :: sl 
} 

भागो के रूप में

perm(2, List(1,2,2,2,1)) 

इस देता है:

List(List(2, 2), List(2, 1), List(1, 2), List(1, 1)) 

के रूप में करने का विरोध किया:

List(
    List(1, 2), List(1, 2), List(1, 2), List(2, 1), 
    List(2, 1), List(2, 1), List(2, 1), List(2, 1), 
    List(2, 1), List(1, 2), List(1, 2), List(1, 2) 
) 

मलिनता नेस्टेड पर्म कॉल के अंदर सूची से एक 'एल' को हटा रहा है, मैं कल्पना है कि करने के लिए एक अच्छा तरीका है, लेकिन मैं एक नहीं सोच सकते हैं ।

Answer 4

मैं अपने ब्लॉग में समस्या के लिए एक समान समाधान लिखा है: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

सबसे पहले मैं सभी संभव संयोजनों पैदा करने और डुप्लिकेट को हटाने, के बारे में सोचा (या सेट का उपयोग, कि दोहराव ही का ख्याल रखता है), लेकिन के रूप में समस्या सूचियों के साथ निर्दिष्ट की गई थी और सभी संभावित संयोजन बहुत अधिक होंगे, मैं समस्या के लिए एक पुनरावर्ती समाधान के साथ आया हूं:

आकार n के संयोजन प्राप्त करने के लिए, सेट का एक तत्व लें और इसे संलग्न करें शेष तत्वों के आकार एन -1 के सेट के सभी संयोजनों के लिए, शेष तत्वों के आकार एन के संयोजन संघ। यही कारण है कि कोड करता है

//P26 
def combinations[A](n:Int, xs:List[A]):List[List[A]]={ 
    def lift[A](xs:List[A]):List[List[A]]=xs.foldLeft(List[List[A]]())((ys,y)=>(List(y)::ys)) 

    (n,xs) match { 
     case (1,ys)=> lift(ys) 
     case (i,xs) if (i==xs.size) => xs::Nil 
     case (i,ys)=> combinations(i-1,ys.tail).map(zs=>ys.head::zs):::combinations(i,ys.tail) 
    } 
} 

यह कैसे पढ़ने के लिए:

मैं एक सहायक समारोह है कि "उठाना" सूचियों

तर्क मैच में है की एक सूची में एक सूची बनाने के लिए किया था कथन:

यदि आप सूची के तत्वों के आकार 1 के सभी संयोजन चाहते हैं, तो केवल सूचियों की एक सूची बनाएं जिसमें प्रत्येक उपन्यासकार में मूल तत्व (जो "लिफ्ट" फ़ंक्शन है)

संयोजन सूची की कुल लंबाई कर रहे हैं, सिर्फ एक सूची है, जिसमें केवल तत्व तत्व सूची है वापसी (केवल एक संभव संयोजन!)

अन्यथा, सिर और सूची की पूंछ ले, पूंछ (रिकर्सिव कॉल) के आकार एन -1 के सभी संयोजनों की गणना करें और परिणामस्वरूप सूचियों में से प्रत्येक को सिर संलग्न करें (.map (ys.head :: zs)) परिणाम n के सभी संयोजनों के साथ परिणाम को जोड़ दें सूची की पूंछ (एक और रिकर्सिव कॉल)

क्या यह समझ में आता है?

Answer 5

स्केला संग्रह के बीच, संयोजन बन गए हैं अभिन्न अंग:

scala> val li = List (1, 1, 0, 0) 
li: List[Int] = List(1, 1, 0, 0) 

scala> li.combinations (2) .toList 
res210: List[List[Int]] = List(List(1, 1), List(1, 0), List(0, 0)) 

हम देखते हैं, यह दोहराव की अनुमति नहीं है, लेकिन उन्हें हालांकि संयोजनों के साथ सरल है अनुमति देने के लिए: हर तत्व की गणना करें अपने संग्रह की (0 li.size -1) और सूची में तत्व को मैप:

scala> (0 to li.length-1).combinations (2).toList .map (v=>(li(v(0)), li(v(1)))) 
res214: List[(Int, Int)] = List((1,1), (1,0), (1,0), (1,0), (1,0), (0,0)) 

Answer 6

यह समाधान Rosetta कोड पर पोस्ट किया गया: http://rosettacode.org/wiki/Combinations_with_repetitions#Scala

def comb[A](as: List[A], k: Int): List[List[A]] = 
    (List.fill(k)(as)).flatten.combinations(k).toList 

Answer 7

यह वास्तव में स्पष्ट नहीं है कि आप क्या पूछ रहे हैं। यह कुछ अलग चीजों में से एक हो सकता है। सबसे पहले सूची में विभिन्न तत्वों के सरल संयोजन होंगे। स्कैला संग्रह से combinations() विधि के साथ प्रदान करता है। यदि तत्व अलग हैं, तो व्यवहार वास्तव में "संयोजन" की शास्त्रीय परिभाषा से अपेक्षा करता है। पी तत्वों के एन-तत्व संयोजनों के लिए पी होगा!/एन! (पी-एन)! आउटपुट में संयोजन।

यदि सूची में दोहराए गए तत्व हैं, हालांकि, स्कैला संयोजन में एक से अधिक बार प्रदर्शित होने वाले आइटम के साथ संयोजन उत्पन्न करेगी। लेकिन केवल अलग-अलग संभावित संयोजन, तत्व के साथ संभवतः इनपुट में मौजूद कई बार दोहराया जाता है। यह केवल संभावित संयोजनों का सेट उत्पन्न करता है, इसलिए तत्वों को दोहराया जाता है, लेकिन संयोजनों को दोहराया नहीं जाता है। मुझे यकीन नहीं है कि अगर अंतर्निहित है तो वास्तविक Set पर एक इटरेटर है।

अब यदि आप सही ढंग से समझते हैं तो वास्तव में क्या मतलब है विभिन्न पी तत्वों के दिए गए सेट से संयोजन, जहां एक संयोजन संयोजन में बार-बार एन बार प्रदर्शित हो सकता है।

ठीक है, इनपुट में बार-बार तत्व होने पर संयोजन उत्पन्न करने के लिए थोड़ा सा वापस आना, और आप आउटपुट में बार-बार संयोजन देखना चाहते हैं, इसके बारे में जाने का तरीका सिर्फ "क्रूर बल" "एन नेस्टेड loops का उपयोग कर। ध्यान दें कि इसके बारे में वास्तव में कुछ भी क्रूर नहीं है, यह केवल संयोजनों की प्राकृतिक संख्या है, वास्तव में, जो छोटे एन के लिए ओ (पी^एन) है, और इसके बारे में आप कुछ भी नहीं कर सकते हैं। आप केवल इस तरह, ठीक से इन मूल्यों को लेने के लिए सावधान रहना चाहिए:

val a = List(1,1,2,3,4) 
def comb = for (i <- 0 until a.size - 1; j <- i+1 until a.size) yield (a(i), a(j)) 

में

scala> comb 
res55: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (1,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)) 

यह एक में इन दोहराया मूल्यों से संयोजन उत्पन्न करता है पहले के रूप में 0 until a.size के मध्यवर्ती संयोजन बनाने के द्वारा जिसके परिणामस्वरूप (i, j) ...

अब "repetitions के साथ संयोजन" बनाने के लिए आप सिर्फ इस तरह के सूचकांक बदलना होगा:

val a = List('A','B','C') 
def comb = for (i <- 0 until a.size; j <- i until a.size) yield (a(i), a(j)) 

का उत्पादन करेगा

List((A,A), (A,B), (A,C), (B,B), (B,C), (C,C)) 

लेकिन मुझे यकीन है सबसे अच्छा तरीका बड़ा संयोजन को यह सामान्यीकरण करने के लिए क्या नहीं कर रहा हूँ।

अब जब मैं इस पोस्ट को मिला, तो मैं उस चीज़ के साथ बंद हूं जो एक इनपुट से संयोजन उत्पन्न करता है जिसमें दोहराए गए तत्व होते हैं, combinations() द्वारा उत्पन्न मध्यस्थ सूचकांक के साथ। यह अच्छा है कि यह विधि एक टुपल की बजाय एक सूची तैयार करती है, इसका मतलब है कि हम वास्तव में "मानचित्र के मानचित्र" का उपयोग करके समस्या का समाधान कर सकते हैं, कुछ मुझे यकीन नहीं है कि किसी और ने यहां प्रस्तावित किया है, लेकिन यह बहुत निफ्टी है और आप इसे देखने के बाद एफपी और स्कैला के लिए अपना प्यार थोड़ा और बढ़ा देंगे!

def comb[N](p:Seq[N], n:Int) = (0 until p.size).combinations(n) map { _ map p } 

परिणाम

scala> val a = List('A','A','B','C') 
scala> comb(a, 2).toList 
res60: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 1), Vector(1, 2), Vector(1, 3), Vector(1, 2), Vector(1, 3), Vector(2, 3))