C++编写程序，输入数n，输出n个字符的全排列，通过函数递归实现。

Question

例如：输入3，得到a、b、c三个字符的全排列为abc,acb,bac,bca,cab,cba。

Answer 1

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<string> do_permutation(string str){
    vector<string> res;
    if (str.size() > 1){
        for (size_t i = 0; i != str.size(); ++i){
            string sub_str = str.substr(0, i) + str.substr(i + 1);
            vector<string> tmp = do_permutation(sub_str);
            for (size_t j = 0; j != tmp.size(); ++j){
                res.push_back(str[i] + tmp[j]);
            }
        }
    }
    else{
        res.push_back(str);
    }
    return res;
}

int main(){
    size_t n;
    cout << "n = ";
    if (cin >> n){
        string str;
        for (size_t i = 0; i != n; ++i){
            str += static_cast<char>('a' + i);
        }
        vector<string> res = do_permutation(str);
        for (size_t i = 0; i != res.size(); ++i){
            cout << res[i] << "\n";
        }
    }
    else{
        cerr << "输入有误\n";
    }
    
    return 0;
}

 

Answer 2

#include <iostream>
using namespace std;

void  output(char d[],int n)       // 输出
{  
      for (int i=0;i<n;i++)
        cout<<d[i];   
  cout<<" ";
}
void swap(char &x, char &y)  //交换
{
char t = x;
x = y;
y = t;
}
void perm(char d[],int n,int j)  //  j起始下标
{
     if (j==n)
           output(d,n);                  // 输出
 else
         for (int i=j;i<n;i++) {
               if (i!=j)
                  swap(d[j],d[i]);     // 交换
               perm(d,n,j+1);    //递归求排列
               if (i!=j)
                  swap(d[j],d[i]);}    //  恢复 
}

int main()
{
char a[] = {'a','b','c','d','e','f','g','h','i','j','k','l',
'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int n;
cout<<"请输入n:\n";
cin>>n;
perm(a,n,0);
cout<<endl;
system("pause");
return 0;
}

算法：1.将第一个字符，依次与后n-1个字符交换值，每次交换得到一个新的首字母；
           2.剩下的n-1个字母按1步骤重复直至所有数组完成排列；