排列问题的递归算法和非递归算法

时间:2021-02-17 04:12:59

参考:算法设计与分析 郑宗汉

原理:

简单地说:第一个数与后面的依次交换!

E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)

然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行

排列生成的代码:

#include<iostream>
using namespace std;
/*
数组a[],元素个数n,后面需要排列的元素个数k
*/
void perm(int a[],int k,int n)
{
    int i;
    if(k==1) 
    {
        for(i=0;i<n;i++) //已构成一个排列,输出它
            cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(i=n-k;i<n;i++) //生成后续k个元素的一系列排列
        {
            swap(a[n-k],a[i]); //元素互换
            perm(a,k-1,n);      //生成后续k-1个元素的一系列排列
            swap(a[n-k],a[i]); //恢复元素原来的位置
        }
    }
}
int main()
{
    int a[]={1,2,3,4,5};
    perm(a,3,5);
}

输出:

12345
12354
12435
12453
12543
12534
请按任意键继续. . .

如果不恢复原来的位置会输出什么?

12345
12354
12534
12543
12345
12354

算法复杂时间度

k=1. 输出n个元素

k=n;对perm(a,k-1,n)执行n次调研,

f(1)=n;

f(n)=nf(n-1);

f(n)=nn!.

 c++ swap函数:

template <class T> void swap ( T& a, T& b )
{
T c(a); a=b; b=c;
}

 上面的解法从后面开始,我们可以从前面开始,比较好理解:

#include<iostream>
using namespace std;
//b表示开始的元素,e表示最后的元素
void perm_aux(int a[],int b,int e) { int i; if(b==e) { for(i=0;i<=e;i++) cout<<a[i]; cout<<endl; } else { for(i=b;i<=e;i++) { swap(a[b],a[i]); perm_aux(a,b+1,e); swap(a[i],a[b]); } } } void perm(int a[],int n) { perm_aux(a,0,n-1); } void perm(int a[],int b,int e) { perm_aux(a,b,e); } int main() { int a[]={1,2,3,4,5}; perm(a,2,4); //生成345的全排列 }

我们重载了perm函数,使其可以直接使用

perm(a,sizeof(a)/sizeof(int))或采用上面的形式。

上面的递归属于指数递归:

排列问题的递归算法和非递归算法

指数递归定义:

An exponential recursive function is one that, if you were to draw out a representation of all the function calls, would have an exponential number of calls in relation to the size of the data set (exponential meaning if there were n elements, there would be O(an) function calls where a is a positive number).

 

上面的代码存在的问题:两个相同的数也进行了交换如果是

{1,2,2}输出:

122
122
212
221
221
212
请按任意键继续. . .

明显不符合要求。

改进后代码:

bool isSwap(int a[],int b,int e)
{
    for(int i=b;i<e;i++)
    {
        if(a[i]==a[e])
            return false;
    }
    return true;
}
void perm_aux(int a[],int b,int e)
{
    int i;
    if(b==e)
    {
        for(i=0;i<=e;i++)
            cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(i=b;i<=e;i++)
        {
           if(isSwap(a,b,i))
           {
            swap(a[b],a[i]);
            perm_aux(a,b+1,e);
            swap(a[i],a[b]);
           }
        }
    }
}

122。输出;

122
212
221
请按任意键继续. . .

i=0 isSwap(0,0) true,perm_aux(a,1,2). 返回false.

i=1 isSwap(a,0,1) 可以交换

i=2 isSwap(a,0,2)  

for(int i=b;i<e;i++)
    {
        if(a[i]==a[e])
            return false;
    }
    return true;

在2前面a[1]=a[2],返回false。不可以交换

重要的是IsSwap函数。

 

 

 更多算法:

http://www.cnblogs.com/bakari/archive/2012/08/02/2620826.html

http://www.cppblog.com/goal00001111/archive/2009/01/20/72378.html

http://hi.baidu.com/tjuer/item/4e2701cae435dc3c44941685