问题描述: 设$R={r_1,r_2,…r_n}$是要进行排列的 n 个元素。其中元素$r_1,r_2,…r_n$可能相同。设设计一个算法，列出 R的所有不同排列。

算法设计: 给定 n及待排列的 n 个元素，计算出这 n个元素的所有不同排列。

数据输入: 由文件 input.txt 提供输入数据。文件的第 1 行是元素个数 n，$1 \leq n \leq 500$。接下来的 n 行是待排列的 n 个元素。

结果输出: 将计算出的 n个元素的所有不同排列输出到文件 output.txt。文件最后 1 行中是排列总数。

input.txt

4
aacc

output.txt

aacc
aacb
acac
acca
caac
caca
ccaa
6

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

/*
以abcd为例，perm(abcd)
1、以a开头，则有bcd,bdc,cbd,cdb,dbc,dcb，记为(a)perm(bcd)；递归定义，perm(bcd)也可以分解为(b)perm(cd), (c)perm(db), (d)perm(bc)...
2、同样，有(b)perm(acd)、(c)perm(adb)、(d)perm(bac)；再继续递归定义...
3、知道最后perm(a), perm(b), perm(c), perm(d),其值为1

对于有重复的字符，只需加一步判断，判断之前出现的递归序列中有没有以该字母开头的情况
*/

int count=0;//记录总的排列数
bool available(string s,int k,int index){//判断是否有以c开头的排列,k为当前递归起始位置，index为当前字符的位置
    char c=s[index];
    for(int i=k;i<index;i++){
        if(s[i]==c) return false;
    }
    return true;
}
void perm(string s,int k,int m){//k为当前位置，m为字符串长度
    if(k==m-1){
        cout<<s<<endl;
        count++;
    }
    else{
        for(int i=k;i<m;i++){ if(!available(s,k,i))continue;//判断是否出现过 swap(s[k],s[i]);//交换当前位置与后面(包括当前位置)的字符,即代表不同字符开头的排列 perm(s,k+1,m); swap(s[k],s[i]);//回溯，恢复原状 } } } int main(){ string s; cin>>s;
    perm(s,0,s.length());
    cout<<"Total permutation number is: "<<count<<endl;
    return 0;
}