处理有重复元素的排列问题——两种方法

抽取法（dfs)

就是在用dfs实现全排列的基础上加上条件限制

#include <iostream>
using namespace std;
int n=4 ;
int cnt = 0;//统计全排列种类数
char tmp[5]="";//定义一个临时数组来保存抽取到的元素
char s[5] = "aabc";
int used[5];//used[i]判断抽取过第i个元素
void dfs(int p)
{
    if(p==n)
    {
        printf("%s\n",tmp);
        cnt++;
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(i>0 && s[i]==s[i-1] &&used[i-1]) continue;
        // 注意这里的条件，需要加上!used[i-1], 在条件成立时才表示让第i个元素成为p位置，i-1被使用，
         //代表进入下一个数的选取，i不应该被跳过
       if(!used[i])//没有使用过
       {

           tmp[p] = s[i];
           used[i] = 1;//标记为使用过
           dfs(p+1);
           used[i] = 0;//回溯
       }
    }
}
int main()
{
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}

STL

   next_permutation：数组元素初始必须是升序的，
                       输出也是按字典序升序的
   prev_permutation：数组元素初始必须是降序的，
                       输出也是按字典序降序的
   头文件：#include<algorithm>

优点：自动排序，自动去重， 代码少， 不容易犯错，推荐使用，这里本蒟弱推荐大家都使用这个

next_permutation：

#include <iostream>
#include<algorithm>//头文件
using namespace std;
int main()
{
    char s[5] = "abc";
    int cnt = 0;
    do
    {
        cout<<s<<endl;
        cnt++;
    }while(next_permutation(s,s+3));//起始位置，左闭右开
    cout<<"总共有："<<cnt<<" 种排列"<<endl;
    return 0;
}

:prev_permutation

#include <iostream>
#include<algorithm>//头文件
using namespace std;
int main()
{
    char s[5] = "cba";
    int cnt = 0;
    do
    {
        cout<<s<<endl;
        cnt++;
    }while(prev_permutation(s,s+3));//起始位置，左闭右开
    cout<<"总共有："<<cnt<<" 种排列"<<endl;
    return 0;
}

废话：

处理有重复元素的排列问题，交换法我后来发现有问题，这里就只上两种方法了。想了解组合问题的博友，请点击组合