Drucken Sie alle Permutationen einer Zeichenfolge in C

Question

Ich lerne Backtracking und Rekursion und ich bin bei einem Algorithmus zum Drucken aller Permutationen einer Zeichenfolge fest. Ich löste es mit der bell algorithm für Permutation, aber ich bin nicht in der Lage, die Rekursionsmethode zu verstehen. Ich suchte im Internet und fand diesen Code:

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)); 
     } 
    } 
} 

Wie wird dieser Algorithmus im Grunde arbeiten vermag ich nicht zu verstehen? Ich habe sogar Trockenlauf versucht!

Wie wird das Backtracking angewendet?

Und ist es effizienter als der Bell-Algorithmus für die Berechnung der Permutation?

Answer 1

Der Algorithmus arbeitet grundsätzlich auf dieser Logik:

Alle Permutationen einer Zeichenkette X das gleiche wie alle Permutationen von jedem möglichen Zeichen in X sind, mit allen Permutationen des String X in ihm ohne diese Buchstaben kombiniert.

Das heißt, daß alle Permutationen von "ABCD" zu sagen, ist es

• "a" verketteten mit allen Permutationen von "bcd"
• "b" mit allen Permutationen von "acd" verketteten
• "c" verketteten mit allen Permutationen von "schlechten"
• "d" verketteten mit allen Permutationen von "BCA"

Dieser Algorithmus in particul ar führt anstelle der Rekursion auf Teilstrings die Rekursion in der Eingabezeichenfolge durch, wobei kein zusätzlicher Speicher zur Zuweisung von Teilstrings verwendet wird. Das "Backtracking" macht die Änderungen an der Zeichenkette rückgängig und belässt sie im ursprünglichen Zustand.

Answer 2

Der Code hat 2 Probleme, beide bezogen auf n, die angenommene Länge der Zeichenfolge. Der Code for (j = i; j <= n; j++) { swap((a+i), (a+j)); ... vertauscht Nullzeichen '\0' der Zeichenfolge und gibt abgeschnittene Codeergebnisse. Überprüfen Sie das Original (i == n), das (i == (n-1)) sein sollte.

Backtracking wird angewendet, indem swap() zweimal wirksam aufgerufen wird, um den ursprünglichen Austausch rückgängig zu machen.

Die Reihenfolge der Komplexität ist die gleiche für Bell-Algorithmus.

#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

Der Code, den Sie gefunden haben, ist korrekt! Der Algorithmus tauscht das aktuelle Zeichen in der Zeichenfolge mit allen nachfolgenden Zeichen aus und ruft die Funktion rekursiv auf. Es ist schwer in Worten zu erklären. Die folgende Abbildung kann Ihnen helfen.

Das Backracking wird im zweiten Swap durchgeführt, um den Effekt des ersten Swaps umzukehren. Das heißt, wir kehren zum ursprünglichen String zurück und tauschen nun das nächste Zeichen im Array mit dem aktuellen Zeichen aus. Die zeitliche Komplexität des Algo. ist O (n * n!), da die Schleife n-mal läuft und die Permutationsfunktion n heißt! mal. (Für die 1. Iteration wird sie n-mal aufgerufen; für die 2. Iteration (n-1) mal usw.).

Quelle: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Answer 4

Rekursion vereinfacht es wirklich:

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

Pseudo-Code:

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

Ich hatte das gleiche Problem bei der Analyse der Ausführung dieses Backtrack-Algorithmus bei GeeksForGeeks. Sehen Sie selbst, wie das ausgeführt wird. Manchmal wirklich Druckwerte helfen, die Ausführung von Programm zu visualisieren

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