遞歸產生排列

我發現遞歸，除了象階乘這樣非常簡單的遞歸外，很難理解。如果我想打印一個字符串的所有排列，讓好講的字符串長度爲5，就像"abcde"，長度7的排列應該是遞歸產生排列

abced 
abdce 
abdec 
abecd 
abedc 
acbde 
acbed 
acdbe 
acdeb 
acebd 
acedb 
adbce 
adbec 
adcbe 
adceb 
adebc 
adecb 
aebcd 
aebdc 
aecbd 
aecdb 
aedbc 
aedcb 
bacde 
baced 
badce 
badec 
baecd 
baedc 
bcade 
bcaed 
...

如果我想要一個遞歸來計算階乘的所有排列5，如4,3,2或1。我應該使用哪種算法？在這個C++庫中是否有任何函數？

假設打印輸出應該是這樣的：

acbd 
bcad 
abc 
bac 
ab 
ba

來源

2016-06-11 JX2612

原始長度是5當然xD – JX2612

你嘗試過什麼嗎？一些代碼也許？ Checkout [面試蛋糕上的這個問題]（https://www.interviewcake.com/question/python/recursive-string-permutations）對於力學的下降解釋 – adamb

5的因子是120 ...我認爲你的意思是排列長度小於或等於5 –

使用遞歸算法，是很像mathematical induction。首先，您需要處理基本案例，然後找到子問題模式。

對於階乘，將問題定義爲階乘n。

鹼情況下，F(0)=1
子問題圖案，F(n)=n!=n*(n-1)!=n*F(n-1)

而對於排列，定義P(E)作爲設定E的所有排列。

鹼情況下，P({}) = {{}}
子問題圖案。考慮置換的過程中，讓我們說我選擇的第一個元素x，然後我們得到了一個子問題，P(E-x)，然後爲每個p in P(E-x)，並x到前面，我們得到了所有的排列開始元素x，迭代x你有所有的排列，又名P(E)。

在C++中，您可以使用next_permutation。

而且從上面的思想的示例代碼是這樣的：

// generate permutation of {a[st], a[st+1], ..., a[ed]} 
void P(char a[], int st, int ed) { 
    if (st > ed) { puts(a); return; } // nothing to generate 
    for (int i=st; i<=ed; ++i) { 
     swap(a[st], a[i]);   // enumerate first element 
     P(a, st+1, ed); 
     swap(a[st], a[i]);   // recover 
    } 
}

檢查它http://ideone.com/zbawY2。

來源

2016-06-11 15:03:57 delta

遞歸產生排列

回答

相關問題