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

本文主要是介绍算法实现题 2-8 有重复元素的排列问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

´问题描述：
设 R={ n
r ,r , ,r 1 2  }是要进行排列的 n 个元素。其中元素 n
r ,r , ,r 1 2  可能相同。试设计
一个算法，列出 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 

#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<cctype>
#include<unordered_set> 
#include<unordered_map> 
#include<fstream>
using namespace std;
map<string,int>mp;
string s;
int n;
ifstream infile("input.txt",ios::in) ;
ofstream outfile("output.txt");
int find(char *list,int k,int m){
	for(int i=k;i<m;i++){
		if(list[i]==list[m]) return 1;
	}
	return 0;
}
void perm(char *list,int k,int m,int &count){
	if(k==m){
		for(int i=0;i<=m;i++){
			outfile<<list[i];
		}
		outfile<<endl;
		count++;
	}
	else{
		for(int i=k;i<=m;i++){
			if(find(list,k,i)==1) continue;
			swap(list[k],list[i]);
			perm(list,k+1,m,count);
			swap(list[k],list[i]);
		}
	}
}
int main(){
	int t=0;
	while(!infile.eof()){
		string x;
		int xx;
		if(!t){
			infile>>xx;
			n=xx;
			t=1;
		}
		else infile>>x;
		s=x;
	} 
	char list[15];
	int count=0;
	for(int i=0;i<s.size();i++){
		list[i]=s[i];
	}
	perm(list,0,n-1,count);
	outfile<<count;
	infile.close();
	outfile.close();
	return 0;
}

这篇关于算法实现题 2-8 有重复元素的排列问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！