递归字符串排列中的交换函数

HERE是我所指的递归字符串排列解决方案。我明白这个算法，但不能理解代码是如何工作的。就像两个掉期在这里工作一样。递归字符串排列中的交换函数

char * full_string; 
void permute(char * str, int length) { 
    if(length == 0) { 
     printf(“%s\n”, full_string); 
     return; 
    } else { 
     for(int i = 0; i < length; ++i) { 
      swap(str[0], str[i]); 
      permute(str+1, length-1); 
      swap(str[0], str[i]); 
     } 
    } 
}

来源

2014-12-19 Shauny

对不起，我可怜的画。该算法基本上像这样运行：

        ABC 
      /     |      \ 
     swap(A,A)    swap(A,B)    swap(A,C) 
     /     |      \ 
     ABC      BAC      CBA 
    /  \    /  \    /  \ 
swap(B,B) swap(B,C) swap(A,A) swap(A,C) swap(B,B) swap(B,A) 
/   \   /   \   /   \ 
ABC    ACB  BAC   BCA  CBA   CAB

记住permute产生最后length元素的所有排列，所以你交换的每个元素与第一元素和去旁边，这样你会得到所有排列。

来源

2014-12-19 08:59:47 justmscs

感谢justmscs ..这是你第三次帮助我。 :)看起来像我们两个正在准备接受采访：ms后面的采访：P ...我们能成为朋友吗？因为这样我们可以更积极地互相帮助:) – Shauny 2014-12-19 09:04:43

并且您对此的时间复杂性有任何想法。 – Shauny 2014-12-19 09:14:52

很高兴。 SO是一个很棒的地方，我在这里学到了很多东西。由于长度为n的字符串具有n！个排列（如果字符是唯一的），因此其复杂度为'n！'。 – justmscs 2014-12-19 09:21:13

请问，如果你知道c/C++，代码是不复杂的。

让我们从else子句开始，因为它是函数的主要功能部分。

for(int i = 0; i < length; ++i) { 
    swap(str[0], str[i]); 
    permute(str+1, length-1); 
    swap(str[0], str[i]);

你应该明白的for循环 - 就像在java中一样。

str是一个char数组（实际上是一个指针，但在很多情况下它们是相同的）。所以str[0]是char数组的第一个元素。

在此代码中会混淆Java程序员的主要部分是str+1 - 将数组添加到数组意味着什么？事实上，str是一个指针而不是数组 - c/C++支持pointers arithmetics。给指针加上一个（基本上）意味着任何未来的引用都会用1来表示。例如s[1]之后加入之后等于s[2]。

我想这些解释后，代码应该清楚。

来源

2014-12-19 08:40:54 elyashiv

不，它不是。我不明白两次掉期背后的逻辑。对于这件事我知道很多。感谢您的回复 – Shauny 2014-12-19 08:42:09

两次交换的逻辑是交换，然后交换回来，所以最后的字符串不会改变下一个例程。 – elyashiv 2014-12-19 08:44:13

可以请你解释一个例子..就像“ABC”..再次感谢 – Shauny 2014-12-19 08:48:01

char * full_string; // String is defined... hopefully you get this 
void permute(char * str, int length) { 
    if(length == 0) { // if the length to permute is 0, string should be as-is. This is the base case of the recursion. 
     printf(“%s\n”, full_string); 
     return; 
    } else { // Otherwise... (Recursive case) 
     for(int i = 0; i < length; ++i) { 
      swap(str[0], str[i]); // Swap the first character with the i-th character 
      permute(str+1, length-1); // Get all permutations with the i-th character as the first character 
      swap(str[0], str[i]); // Get the original string back for the next loop 
     } 
    } 
}

要理解的最难的部分是递归位。试着用一个简单的例子来描述它是如何工作的，你应该看看它是如何工作的。

本质上是一个字符串'abc'找到的a + permutations('bc')的情况下，这打破了寻找ab + permutations('c')和'ac' + permutations('b')，这你想要的所有排列'a' + permutations('bc')，'b' + permutations('ac')，并且'c' + permutations('ab')

所有排列然后（例如）下一个递归调用只会让你'abc'和'acb'。

然后在'b'是您的第一个字符并且'c'是您的第一个字符的情况下完成相同的过程。

希望你可以看到这个同样的过程如何打破一个更大的串入找到的第一个字符的排列+剩余的字符的所有排列

来源

2014-12-19 08:43:09 rfj001

递归字符串排列中的交换函数

回答

相关问题