सी

Question

में एक स्ट्रिंग के सभी क्रमपरिवर्तन मुद्रित करें मैं बैकट्रैकिंग और रिकर्सन सीख रहा हूं और मैं स्ट्रिंग के सभी क्रमपरिवर्तनों को मुद्रित करने के लिए एल्गोरिदम पर फंस गया हूं। मैंने क्रमपरिवर्तन के लिए bell algorithm का उपयोग करके हल किया लेकिन मैं रिकर्सन विधि को समझने में सक्षम नहीं हूं। मैं वेब खोज की है और इस कोड को मिला:

void permute(char *a, int i, int n) 
{ 
    int j; 
    if (i == n) 
    printf("%s\n", a); 
    else 
    { 
     for (j = i; j <= n; j++) 
     { 
      swap((a+i), (a+j)); 
      permute(a, i+1, n); 
      swap((a+i), (a+j)); 
     } 
    } 
} 

कैसे इस एल्गोरिथ्म मूल रूप से काम कर रहा है मुझे समझ में नहीं कर पा रहा हूँ? मैंने सूखी दौड़ने की भी कोशिश की!

बैकट्रैकिंग कैसे लागू होती है?

और यह क्रमपरिवर्तन की गणना के लिए बेल एल्गोरिदम से अधिक कुशल है?

Answer 1

एल्गोरिथ्म मूल रूप से इस तर्क पर काम करता है:

एक स्ट्रिंग एक्स के सभी क्रमपरिवर्तन एक्स में प्रत्येक संभव चरित्र के सभी क्रमपरिवर्तन, उस में उस पत्र के बिना स्ट्रिंग एक्स के सभी क्रमपरिवर्तन के साथ संयुक्त रूप में एक ही बात है।

कहना है कि, "एबीसीडी" के सभी क्रमपरिवर्तन हैं

• "बीसीडी"
• "बी" "एसीडी" के सभी क्रमपरिवर्तन साथ concatenated
• के सभी क्रमपरिवर्तन के साथ "एक" श्रेणीबद्ध "सी" "बुरा"
• "डी" के सभी क्रमपरिवर्तन "बीसीए"

particul में इस एल्गोरिथ्म के सभी क्रमपरिवर्तन साथ concatenated साथ concatenated सबस्ट्रिंग्स पर रिकर्सन करने के बजाय ar, सबस्ट्रिंग आवंटित करने के लिए कोई अतिरिक्त मेमोरी का उपयोग करते हुए इनपुट स्ट्रिंग पर जगह पर रिकर्सन करता है। "बैकट्रैकिंग" स्ट्रिंग में परिवर्तन को पूर्ववत करता है, इसे अपने मूल स्थिति में छोड़ देता है।

Answer 2

कोड में 2 समस्या है, दोनों स्ट्रिंग की अनुमानित लंबाई n से संबंधित हैं। कोड for (j = i; j <= n; j++) { swap((a+i), (a+j)); ... स्ट्रिंग के शून्य वर्ण '\0' में स्वैप करें और कोड छंटनी परिणाम देता है। मूल (i == n) देखें जो (i == (n-1)) होना चाहिए।

बैकट्रैकिंग swap() पर कॉल करके लागू किया जाता है जो दो बार अपने मूल स्वैप को पूर्ववत करता है।

बेल एल्गोरिदम के लिए जटिलता का क्रम समान है।

#include <stdio.h> 

void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; } 

void permute(char *a, int i, int n) { 
    // If we are at the last letter, print it 
    if (i == (n-1)) printf("%s\n", a); 
    else { 
    // Show all the permutations with the first i-1 letters fixed and 
    // swapping the i'th letter for each of the remaining ones. 
    for (int j = i; j < n; j++) { 
     swap((a+i), (a+j)); 
     permute(a, i+1, n); 
     swap((a+i), (a+j)); 
    } 
    } 
} 

char s[100]; 
strcpy(s, "ABCD"); 
permute(s, 0, strlen(s)); 

Answer 3

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

बैकअप कुछ स्वैप के प्रभाव को उलटने के लिए दूसरे स्वैप में किया जा रहा है यानी हम मूल स्ट्रिंग पर वापस जा रहे हैं और अब वर्तमान चरित्र के साथ सरणी में अगले चरित्र को स्वैप कर देंगे। अलगो की समय जटिलता। ओ (एन * एन!) है क्योंकि लूप एन बार चलाता है और परमिट फ़ंक्शन को एन कहा जाता है! बार। (पहली पुनरावृत्ति के लिए, इसे एन बार कहा जाता है; दूसरे पुनरावृत्ति (एन -1) बार और इसी तरह के लिए)।

स्रोत: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Answer 4

Recursion वास्तव में इसे सरल:

public static void permutation(String str) 
{ 
    permutation("", str); 
} 

private static void permutation(String prefix, String str) 
{ 
    int n = str.length(); 
    if (n == 0) { 
     System.out.println(prefix); 
    } else { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
    } 
} 

Answer 5

# include <stdio.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 i, int n) 
{ 
    int j; 
    if (i == n) 
     printf("%s\n", a); 
    else 
    { 
      for (j = i; j <= n; j++) 
     { 
      swap((a+i), (a+j)); 
      permute(a, i+1, n); 
      swap((a+i), (a+j)); //backtrack 
     } 
    } 
} 

/* Driver program to test above functions */ 
int main() 
{ 
    char a[] = "ABC"; 
    permute(a, 0, 2); 
    getchar(); 
    return 0; 
} 

Answer 6

छद्म कोड:

String permute(String a[]) 
{ 
    if (a[].length == 1) 
    return a[]; 
    for (i = 0, i < a[].length(); i++) 
    append(a[i], permute(a[].remove(i))); 
} 

Answer 7

I create more specific but not efficient Program for permutation for general string. 
It's work nice way. 
//ubuntu 13.10 and g++ compiler but it's works on any platform and OS 
//All Permutation of general string. 

#include<iostream> 
#include<stdio.h> 
#include<string> 
#include<string.h> 
using namespace std; 
int len; 
string str; 

void permutation(int cnum) 
{ 
    int mid; 
    int flag=1; 
    int giga=0; 
    int dead=0; 
    int array[50]; 
    for(int i=0;i<len-1;i++) 
    { 
     array[50]='\0'; 
     dead=0; 
     for(int j=cnum;j<len+cnum;j++) 
     { 
      mid=j%len; 
      if(mid==cnum && flag==1) 
      { 
       cout<<str[mid]; 
       array[dead]=mid; 
       dead++; 
       flag=0; 
      } 
       else 
      { 
       giga=(i+j)%len; 
       for(int k=0;k<dead;k++)     
       { 
        if((array[k]==giga) && flag==0) 
        { 
        giga=(giga+1)%len; 
        } 
       } 
       cout<<str[giga]; 
       array[dead]=giga; 
       dead++; 

      } 
     } 
     cout<<endl; 
     flag=1; 
    } 
} 
int main() 
{ 
    cout<<"Enter the string :: "; 
    getline(cin,str); 
    len=str.length(); 
    cout<<"String length = "<<len<<endl; 
    cout<<"Total permutation = "<<len*(len-1)<<endl; 
    for(int j=0;j<len;j++) 
    { 
     permutation(j); 
    } 
return 0; 
} 

Answer 8

मुझे GeeksForGeeks पर इस बैकट्रैक एल्गोरिदम के निष्पादन का विश्लेषण करने में एक ही समस्या का सामना करना पड़ा। अपने आप को देखें कि यह कैसे निष्पादित करता है। कभी कभी मुद्रण मूल्यों वास्तव में कार्यक्रम

swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC 
permute(a, l+1, r); ==== Values send to permute i.e. string= ABC //////// (l+1) = 1 //////// r = 2 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC 
permute(a, l+1, r); ==== Values send to permute i.e. string= ABC //////// (l+1) = 2 //////// r = 2 
ABC 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ACB 
permute(a, l+1, r); ==== Values send to permute i.e. string= ACB //////// (l+1) = 2 //////// r = 2 
ACB 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ABC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i));++++ Backtract swap //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 0 //////// r = 2 //////// string = BAC 
permute(a, l+1, r); ==== Values send to permute i.e. string= BAC //////// (l+1) = 1 //////// r = 2 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC 
permute(a, l+1, r); ==== Values send to permute i.e. string= BAC //////// (l+1) = 2 //////// r = 2 
BAC 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BCA 
permute(a, l+1, r); ==== Values send to permute i.e. string= BCA //////// (l+1) = 2 //////// r = 2 
BCA 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BAC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 0 //////// r = 2 //////// string = ABC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 0 //////// r = 2 //////// string = CBA 
permute(a, l+1, r); ==== Values send to permute i.e. string= CBA //////// (l+1) = 1 //////// r = 2 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA 
permute(a, l+1, r); ==== Values send to permute i.e. string= CBA //////// (l+1) = 2 //////// r = 2 
CBA 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CAB 
permute(a, l+1, r); ==== Values send to permute i.e. string= CAB //////// (l+1) = 2 //////// r = 2 
CAB 
______________________________________________________________________ 
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CBA 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 0 //////// r = 2 //////// string = ABC 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
------------------------------END OF BACKTRACK-------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 
--------------------------------------------------------------------------------------------------------- 

Answer 9

def perms(s): 
    if len(s) < 1: 
     return [s] 
    ps = [] 
    for i in range(0, len(s)): 
     head, tail = s[i], s[0:i] + s[i + 1:] 
     ps.extend([head + tailp for tailp in perms(tail)]) 
    return ps