递归算法：求序列的全排列

清疚 2022-03-28 08:20 211阅读 0赞

## 用C++模板书写一段序列数组的所有排列 ##

/**
    * 书本:【windows程序设计】
    * 功能:输出所有的排列情况
    * 文件:全排列.cpp
    * 时间:2014年9月29日21:52:55
    * 作者:cutter_point
    */
    
    #include <iostream>
    
    using namespace std;
    
    //交换两个元素的函数
    template<class Type>
    inline void Swap(Type &a, Type &b)  //取两个元素的引用，等会来交换
    {
        Type temp=a;
        a=b;
        b=temp;
    }
    
    //这个是一个递归为了输出所有的排列情况
    template<class Type>
    void Perm(Type list[], int k, int m)
    {
        //这个函数是为了产生所有的排列情况
        if(k == m)  //就是当k和m相等的时候，就输出序列
        {//就是剩下一个元素的时候
            for(int i=0 ; i <= m ; ++i)
                cout<<list[i]<<' ';
            cout<<endl;
        }
        else    //还有多个元素等待排列，递归产生排列
        {
            for(int i=k ; i <= m ; ++i) //从第k个開始吧第k个和i个交换输出
            {
                Swap(list[k], list[i]); //交换第k和第i个元素
                Perm(list, k+1, m);     //仅仅要不是最后一个，就是第二个參数不是最后一个时,调用自己
                Swap(list[i], list[k]); //换回来，进行下一个排列的变换
            }
        }
    }
    
    
    
    int main()
    {
        int n;      //要进行排序的个数
        //定义一个序列的个数
        cout<<"输入你想要进行排序的个数"<<endl;
        cin>>n;
        int a[n];   //存放所有的个数
        cout<<"输入序列:"<<endl;
        for(int i=0 ; i < sizeof(a)/sizeof(int) ; ++i)
            cin>>a[i];
    
        cout<<"所有的排序结果:"<<endl;
        Perm(a, 0, sizeof(a)/sizeof(int)-1);
    
        int m;      //要进行排序的个数
        //定义一个序列的个数
        cout<<"输入你想要进行排序的字符个数"<<endl;
        cin>>m;
        char b[m];   //存放所有的个数
        cout<<"输入字符序列:"<<endl;
        for(int i=0 ; i < sizeof(b)/sizeof(char) ; ++i)
            cin>>b[i];
    
        cout<<"所有的排序结果:"<<endl;
        Perm(b, 0, sizeof(b)/sizeof(char)-1);
    
        return 0;
    }

我在想我是接下来搞算法还是搞QT呢？？？？