遞歸字符串排列中的交換函數

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

遞歸字符串排列中的交換函數

回答

相關問題