कुछ कोड लिखने की कोशिश कर रहा है जो एक इनपुट स्ट्रिंग के सभी क्रमपरिवर्तन को रिकर्सन अभ्यास के रूप में उत्पन्न करता है लेकिन यह नहीं समझ सकता कि मुझे स्टैक ओवरफ़्लो त्रुटि क्यों मिलती है।

fun main() {
    println(subSet(listOf("abcd")))
}

fun subSet(s: List<String>): List<String>{
    return listOf<String>() + createSubSets(s)
}

fun createSubSets(s: List<String>): List<String>{
    if(s.isEmpty()){
        return listOf()
    }
    return s.mapIndexed{i, elem ->
        elem + createSubSets(s.drop(i))
    }
}
1
Maks 23 मार्च 2020, 13:09

4 जवाब

यह कथन अनंत पुनरावृत्ति की ओर ले जाता है:

return s.mapIndexed { i, elem ->
    elem + createSubSets(s.drop(i))
}

इसमें, पहले पुनरावृत्ति में i का मान 0 (elem के साथ सूचकांक 0) का वर्ण है, और पुनरावर्ती कॉल createSubSets(s.drop(i)) है createSubSets(s) के बराबर, क्योंकि एक स्ट्रिंग से शून्य वर्ण छोड़ने से मूल स्ट्रिंग वापस आ जाती है।

0
hotkey 23 मार्च 2020, 13:42

आपका पुनरावर्ती कार्य सुरक्षित नहीं है। यह हमेशा के लिए पुनरावृत्त होता है, स्टैक में जुड़ता रहता है और इसीलिए आपको स्टैक ओवरफ़्लो मिल रहा है।

अपने एल्गोरिथ्म को ठीक करने के अलावा, आप स्थिति को सुधारने के लिए दो काम कर सकते हैं:

  1. फ़ंक्शन को अंततः बाहर निकलने के लिए बाहर निकलने की स्थिति जोड़ें।
fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s, 0)
}

fun createSubSets(s: List<String>, index: Int): List<String> {
    if (index > s.lastIndex) {
        return emptyList()
    }
    val otherElements = s.subList(0, index) + s.subList(index + 1, s.size)
    val element = s[index]
    return otherElements.map { element + it } + createSubSets(s, index + 1)
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
  1. फ़ंक्शन को tail-recursive बनाएं ताकि लंबे स्ट्रिंग्स के साथ भी यह ओवरफ़्लो को स्टैक न करे।
fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s, 0, emptyList())
}

tailrec fun createSubSets(s: List<String>, index: Int, carryOn: List<String>): List<String> {
    if (index > s.lastIndex) {
        return carryOn
    }
    val otherElements = s.subList(0, index) + s.subList(index + 1, s.size)
    val element = s[index]
    return createSubSets(s, index + 1, carryOn + otherElements.map { element + it })
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]

ध्यान दें कि टेल-रिकर्सिव वर्जन हमेशा खुद को आखिरी चीज कहता है। विशेष रूप से, यह स्वयं को कॉल करने के परिणाम पर कोई संचालन नहीं करता है। इसलिए इसे परिणाम को अगली कॉल पर ले जाना है, लेकिन यही कारण है कि यह सुरक्षित है।

अंत में, ध्यान दें कि इस समस्या को हल करने के लिए आपको बिल्कुल भी रिकर्सन की आवश्यकता नहीं है:

fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s)
}

fun createSubSets(s: List<String>): List<String> {
    return s.mapIndexed { i, element ->
        val otherElements = s.subList(0, i) + s.subList(i + 1, s.size)

        otherElements.map { element + it }
    }.flatten()
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
0
Jakub Zalas 23 मार्च 2020, 14:39

एक और उदाहरण:

fun String.permute(result: String = ""): List<String> =
    if (isEmpty()) listOf(result) else flatMapIndexed { i, c -> removeRange(i, i + 1).permute(result + c) }

fun main() {
    println("abc".permute()) // [abc, acb, bac, bca, cab, cba]
}
1
Tatsuya Fujisaki 29 मार्च 2021, 12:15
fun main() {
permutations("abcd","")   }
                                         
fun permutations(str:String, storedString: String){
if(str.length == 1)
    println(storedString+str)
else
for(i in str.indices)
    permutations(str.removeRange(i,i+1),storedString+str[i])}
0
Mohamad_Dan 30 नवम्बर 2020, 14:04
आपको अपना कोड थोड़ा सा समझाने की जरूरत है। आपके कोड के लिए कोई स्पष्टीकरण आपके उत्तर को और अधिक उपयोगी बना देगा।
 – 
A. Badakhshan
30 नवम्बर 2020, 14:20
यह फ़ंक्शन इनपुट स्ट्रिंग "str" ​​के माध्यम से पुनरावृति करता है, प्रत्येक पुनरावृति यह वर्तमान अनुक्रमणिका पर चार ले जाएगा और इसे "संग्रहीतस्ट्रिंग" में जोड़ देगा और शेष स्ट्रिंग str के लिए खुद को याद करेगा, इस प्रकार जब str में केवल एक वर्ण होता है तो हमारे पास होगा एक क्रमपरिवर्तन मिला है तो वह इसे प्रिंट करेगा।
 – 
Mohamad_Dan
30 नवम्बर 2020, 15:37