递归产生排列

我发现递归，除了象阶乘这样非常简单的递归外，很难理解。如果我想打印一个字符串的所有排列，让好讲的字符串长度为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

递归产生排列

回答

相关问题