я не могу понять, как этот код работает

Question

Это с программой, чтобы выяснить все возможные комбинации с одним словом ->

# 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 1

Возможно, у вас есть проблема в понимании техники возврата. В этом случае вы должны немного прочитать об этом: http://en.wikipedia.org/wiki/Backtracking

Однако код работает от символа в позиции от 0 до 2 следующих символов. Он меняет первый символ следующим образом и называет себя следующей стартовой точкой. Наконец, верните символы, чтобы воссоздать ситуацию.

На первом уровне рекурсии функция переключения на первую букву и назвать себя для следующих двух:

permute("ABC", 1, 2) 
permute("BAC", 1, 2) 
permute("CBA", 1, 2) 

второй уровень рекурсии:

permute("ABC", 2, 2) /* -> printf ABC */ 
permute("ACB", 2, 2) /* -> printf ACB */ 

permute("BAC", 2, 2) /* -> printf BAC */ 
permute("BCA", 2, 2) /* -> printf BCA */ 

permute("CBA", 2, 2) /* -> printf CBA */ 
permute("CAB", 2, 2) /* -> printf CAB */ 

Answer 2

Возьмите этот код и запустить его , слишком ленив, чтобы написать все этапы, почему бы не позволить компьютеру это делать?

# include <stdio.h> 

/* Function to swap values at two pointers */ 
void swap (char *x, char *y) 
{ 
    char temp; 
    printf("Swapping %c with %c\n",*x,*y); //<---------- I ADDED THIS FOR YOU 
    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; 
    printf("-----Now in permute(a,%d,%d)-----\n",i,n); //<---------- I ADDED THIS FOR YOU 
    printf("-----String is now %s-----\n",a); //<---------- I ADDED THIS FOR YOU 
    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; 
}