字符串排列 - 这个回溯递归是如何工作的? [英] String permutation - How does this backtracking recursion work?

问题描述

这个函数基本上通过将一个字符与其所有其他字符交换来打印字符串的所有可能排列.我理解前两个调用交换和置换.但是为什么第二次调用 swap 呢?我无法理解这段代码.有人可以解释一下这是如何工作的吗?

This function basically prints all possible permutations of a string by swapping a character with all its other characters. I understand the first two calls to swap and permute. But why is swap called for the second time? I cannot understand this piece of code. Can someone please explain me how this works?

/* 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
       }
   }
}

推荐答案

回溯"将字符串交换回其原始状态，这对于算法的正确运行至关重要.

The "backtrack" swaps the string back to its original state, which is vital for the correct running of the algorithm.

您不希望您的函数弄乱您的输入字符串，对吗?

You wouldn't want your function to mess up your input string, would you?

这篇关于字符串排列 - 这个回溯递归是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！