递归实现全排列(可包含重复元素)

  • Post author:
  • Post category:其他


生成一个数组中元素的全排列(重复元素,只出现一次)


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char input[3],output[3];

void dfs(int k,int n)
{
    if(k==n){//递归边界
        for(int i=0;i<n;i++){
            printf("%c,",output[i]);
        }
        printf("\n");
    }
    else{
        for(int i=0;i<n;i++){
            if(!i||input[i]!=input[i-1]){//由于input数组已经排序,所以只需要检查input的第一个元素和所有“与前一个元素不相同得元素”
                int cnt1=0,cnt2=0;
                for(int j=0; j<k; j++)
                    if(output[j]==input[i])//统计output[0]~output[k-1]中input[i]出现的次数
                        cnt1++;
                for(int j=0; j<n; j++)//统计input数组中input[i]出现的次数
                    if(input[i]==input[j])
                        cnt2++;
                if(cnt1<cnt2)
                {
                    output[k]=input[i];
                    dfs(k+1,n);
                }
            }

        }
    }
}
int main()
{
    scanf("%s",input);
    sort(input,input+3);//输入数组必须排序
    dfs(0,3);
    return 0;
}






版权声明:本文为huanhuanxiaoxiao原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。