算法实现题 2-8 有重复元素的排列问题

问题描述：

设 R={ r1 , r2 ,··· , rn }是要进行排列的 n 个元素。其中元素 r1 , r2 , ··· , rn 可能相同。试设计一个算法，列出 R 的所有不同排列。

编程任务：

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

数据输入：

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

结果输出:

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

输入文件示例

input.txt
4
aacc

输出文件示例

output.txt
aacc
acac 
acca 
caac 
caca 
ccaa 
6 

注意

fgets 读取文件 只能是 char * 而不能是 string

递归遍历

当第一个字符与第i个字符交换后，记得变回来

代码：

#include <iostream>
#include <set>
#include <vector>
#define MaxSize 1000010

using namespace std;
int count=0;
int n;
char ch[MaxSize]; //取字符串
char str[10]; //取数字

char st[MaxSize]; //取answer

void func(vector<string> ve,string str,int begin,int end)
{
    if(begin==end)
    {
        count++;
        ve.push_back(str);
    }
    set<char> s;
    set<char>::iterator it;
    for(int i=begin; i<=end; i++)
    {
        if(s.find(str[i])==s.end())
        {
            swap(str[begin],str[i]);
            func(ve,str,begin+1,end);
            swap(str[begin],str[i]);
            s.insert(str[i]);
        }
    }


}
int main()
{


    bool flag=true;
    for(int k=0; k<=10; k++)
    {
        string path1="F:\\算法\\实验组2-分治-实验包\\prog25\\test\\perm"+to_string(k)+".in";
        FILE* f=fopen(path1.c_str(),"r");
        fgets(str,10,f);
        n=stoi(str);
        fgets(ch,n+1,f);
        string str1="";
        vector<string> ve;
        for(int i=0; i<=n; i++)
        {
            str1=str1+ch[i];
        }
        str1=str1.substr(0,n);
        func(ve,str1,0,n-1);
        string path2="F:\\算法\\实验组2-分治-实验包\\prog25\\answer\\perm"+to_string(k)+".out";
        FILE* fp=fopen(path2.c_str(),"r");
        vector<string> ve2;
        while(fgets(st,MaxSize,fp))
        {

            string str3="";
            for(int i=0; i<n; i++)
            {
                str3=str3+st[i];
            }
            ve2.push_back(str3);
        }
        for(int i=0; i<ve.size(); i++)

        {
            if(ve[i]!=ve2[i])
            {
                flag=false;
                cout << "第" << k << "个测试用例未通过" << endl;
                cout << ve[i] << "%%" << ve2[i] << endl;
                break;
            }
        }
        for(int i=0;i<ve.size();i++)
            cout << ve[i] << "&" << endl;
        ve.clear();
        ve2.clear();
        fclose(f);
        fclose(fp);
    }
    if(flag)
        cout << "测试用例全部通过" << endl;

}