क्रमपरिवर्तन उत्पन्न करने के लिए रिकर्सन को समझना

Question

मुझे पुनरावृत्ति मिलती है, तथ्यों के समान बहुत सीधे आगे के अलावा, समझने में बहुत मुश्किल होती है। निम्न स्निपेट स्ट्रिंग के सभी क्रमपरिवर्तन प्रिंट करता है। क्या कोई इसे समझने में मेरी सहायता कर सकता है। रिकर्सन को सही तरीके से समझने का तरीका क्या है।

void permute(char a[], int i, int n) 
{ 
    int j; 
    if (i == n) 
    cout << a << endl; 
    else 
    { 
     for (j = i; j <= n; j++) 
     { 
      swap(a[i], a[j]);   
      permute(a, i+1, n); 
      swap(a[i], a[j]); 
     } 
    } 
} 

int main() 
{ 
    char a[] = "ABCD"; 
    permute(a, 0, 3); 
    getchar(); 
    return 0; 
} 

Answer 1

PaulR सही सुझाव है। जब तक आप इसे समझ नहीं लेते हैं, आपको "हाथ" (कोड जो भी टूल्स आप चाहते हैं - डीबगर्स, पेपर, लॉगिंग फ़ंक्शन कॉल और कुछ बिंदुओं पर चर) का उपयोग करके कोड को चलाने के लिए है। कोड के स्पष्टीकरण के लिए मैं आपको quasiverse के उत्कृष्ट उत्तर के बारे में बताऊंगा।

शायद एक थोड़ा छोटे तार के साथ कॉल ग्राफ के इस दृश्य यह और भी स्पष्ट यह कैसे काम करता है:

ग्राफ graphviz साथ किया गया था।

// x.dot 
// dot x.dot -Tpng -o x.png 
digraph x { 
rankdir=LR 
size="16,10" 

node [label="permute(\"ABC\", 0, 2)"] n0; 
node [label="permute(\"ABC\", 1, 2)"] n1; 
    node [label="permute(\"ABC\", 2, 2)"] n2; 
    node [label="permute(\"ACB\", 2, 2)"] n3; 
node [label="permute(\"BAC\", 1, 2)"] n4; 
    node [label="permute(\"BAC\", 2, 2)"] n5; 
    node [label="permute(\"BCA\", 2, 2)"] n6; 
node [label="permute(\"CBA\", 1, 2)"] n7; 
    node [label="permute(\"CBA\", 2, 2)"] n8; 
    node [label="permute(\"CAB\", 2, 2)"] n9; 

n0 -> n1 [label="swap(0, 0)"]; 
n0 -> n4 [label="swap(0, 1)"]; 
n0 -> n7 [label="swap(0, 2)"]; 

n1 -> n2 [label="swap(1, 1)"]; 
n1 -> n3 [label="swap(1, 2)"]; 

n4 -> n5 [label="swap(1, 1)"]; 
n4 -> n6 [label="swap(1, 2)"]; 

n7 -> n8 [label="swap(1, 1)"]; 
n7 -> n9 [label="swap(1, 2)"]; 
} 

Answer 2

यह सब संभव पात्रों से प्रत्येक चरित्र चुनता छोड़ दिया:

void permute(char a[], int i, int n) 
{ 
    int j; 
    if (i == n)     // If we've chosen all the characters then: 
     cout << a << endl;  // we're done, so output it 
    else 
    { 
     for (j = i; j <= n; j++) // Otherwise, we've chosen characters a[0] to a[j-1] 
     {      // so let's try all possible characters for a[j] 
      swap(a[i], a[j]); // Choose which one out of a[j] to a[n] you will choose 
      permute(a, i+1, n); // Choose the remaining letters 
      swap(a[i], a[j]); // Undo the previous swap so we can choose the next possibility for a[j] 
     } 
    } 
} 

Answer 3

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

फिर आपको रिकर्सन "डाउनिंग आउट" कहने के लिए एक तरीका चाहिए। चूंकि प्रत्येक नई उप-समस्या आखिरी से छोटी है, शायद आप अंततः उप-उप-समस्या प्राप्त कर लेंगे जिसे आप वास्तव में हल करने के बारे में जानते हैं।

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

Answer 4

हालांकि यह छोटा पुराना प्रश्न है और पहले से ही नए आगंतुकों की सहायता के लिए मेरे इनपुट जोड़ने के बारे में सोचा गया है। रिकर्सिव रिकॉन्सीलेशन पर ध्यान दिए बिना चलने वाले समय की व्याख्या करने की योजना बना रहे हैं।

मैंने सी # में नमूना लिखा है लेकिन अधिकांश प्रोग्रामर के लिए समझना आसान है।

static int noOfFunctionCalls = 0; 
static int noOfCharDisplayCalls = 0; 
static int noOfBaseCaseCalls = 0; 
static int noOfRecursiveCaseCalls = 0; 
static int noOfSwapCalls = 0; 
static int noOfForLoopCalls = 0; 

static string Permute(char[] elementsList, int currentIndex) 
{ 
    ++noOfFunctionCalls; 

    if (currentIndex == elementsList.Length) 
    { 
     ++noOfBaseCaseCalls;   
     foreach (char element in elementsList) 
     { 
      ++noOfCharDisplayCalls; 

      strBldr.Append(" " + element); 
     } 
     strBldr.AppendLine(""); 
    } 
    else 
    { 
     ++noOfRecursiveCaseCalls; 

     for (int lpIndex = currentIndex; lpIndex < elementsList.Length; lpIndex++) 
     { 
      ++noOfForLoopCalls; 

      if (lpIndex != currentIndex) 
      { 
       ++noOfSwapCalls; 
       Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]); 
      } 

      Permute(elementsList, (currentIndex + 1)); 

      if (lpIndex != currentIndex) 
      { 
       Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]); 
      } 
     } 
    } 
    return strBldr.ToString(); 
} 

static void Swap(ref char Char1, ref char Char2) 
{ 
    char tempElement = Char1; 
    Char1 = Char2; 
    Char2 = tempElement; 
}  

public static void StringPermutationsTest() 
{ 
    strBldr = new StringBuilder(); 
    Debug.Flush(); 

    noOfFunctionCalls = 0; 
    noOfCharDisplayCalls = 0; 
    noOfBaseCaseCalls = 0; 
    noOfRecursiveCaseCalls = 0; 
    noOfSwapCalls = 0; 
    noOfForLoopCalls = 0; 

    //string resultString = Permute("A".ToCharArray(), 0); 
    //string resultString = Permute("AB".ToCharArray(), 0); 
    string resultString = Permute("ABC".ToCharArray(), 0); 
    //string resultString = Permute("ABCD".ToCharArray(), 0); 
    //string resultString = Permute("ABCDE".ToCharArray(), 0); 

    resultString += "\nNo of Function Calls : " + noOfFunctionCalls; 
    resultString += "\nNo of Base Case Calls : " + noOfBaseCaseCalls; 
    resultString += "\nNo of General Case Calls : " + noOfRecursiveCaseCalls; 
    resultString += "\nNo of For Loop Calls : " + noOfForLoopCalls; 
    resultString += "\nNo of Char Display Calls : " + noOfCharDisplayCalls; 
    resultString += "\nNo of Swap Calls : " + noOfSwapCalls; 

    Debug.WriteLine(resultString); 
    MessageBox.Show(resultString);  
} 

कदम: उदा के लिए जब हम इनपुट को "एबीसी" के रूप में पास करते हैं।

1. पहली बार मुख्य से नामित क्रमिक विधि। तो इंडेक्स 0 के साथ कॉल करना और यह पहला कॉल है।
2. लूप के लिए दूसरे भाग में हम प्रत्येक बार 0 से 2 बनाने के लिए दो बार दोहरा रहे हैं।
3. प्रत्येक लूप के तहत हम एलपीसीएनटी + 1. 4.1 के साथ रिकर्सिव कॉलिंग कर रहे हैं 4.1 जब सूचकांक 1 है तो 2 रिकर्सिव कॉल। 4.2 जब सूचकांक 2 है तो 1 रिकर्सिव कॉल।

तो बिंदु 2 से 4.2 कुल कॉल प्रत्येक लूप के लिए 5 हैं और कुल 15 कॉल + मुख्य प्रविष्टि कॉल = 16 है। हर बार loopCnt 3 है तो अगर स्थिति निष्पादित हो जाती है।

आरेख से हम लूप गिनती 3 कुल 6 बार बन सकते हैं यानी 3 यानी इनपुट "एबीसी" लंबाई का फैक्टोरियल मान।

यदि लूप के लिए स्टेटमेंट "एनबीसी" उदाहरण से अक्षर प्रदर्शित करने के लिए 'एन' बार दोहराता है, तोकुल 6 गुना (फैक्टोरियल टाइम्स) हम क्रमपरिवर्तन प्रदर्शित करने के लिए दर्ज करते हैं। तो कुल चलने का समय = एन एक्स एन!

मैंने प्रत्येक स्थिर निष्पादन को विस्तार से समझने के लिए कुछ स्थिर कॉलकंट चर और तालिका दी है।

विशेषज्ञ, मेरे उत्तर या टिप्पणी को संपादित करने के लिए स्वतंत्र महसूस करें यदि मेरे कोई भी विवरण स्पष्ट या गलत नहीं है, तो मैं उन्हें खुश कर रहा हूं।

Download the sample code and other samples from here

Answer 5

यह कोड और संदर्भ आप इसे समझने के लिए मदद कर सकता है।

// C program to print all permutations with duplicates allowed 
#include <stdio.h> 
#include <string.h> 

/* Function to swap values at two pointers */ 
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

/* Function to print permutations of string 
    This function takes three parameters: 
    1. String 
    2. Starting index of the string 
    3. Ending index of the string. */ 
void permute(char *a, int l, int r) 
{ 
    int i; 
    if (l == r) 
    printf("%s\n", a); 
    else 
    { 
     for (i = l; i <= r; i++) 
     { 
      swap((a+l), (a+i)); 
      permute(a, l+1, r); 
      swap((a+l), (a+i)); //backtrack 
     } 
    } 
} 

/* Driver program to test above functions */ 
int main() 
{ 
    char str[] = "ABC"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
} 

संदर्भ: Geeksforgeeks.org