8594 有重复元素的排列问题(必做)
时间限制:1000MS 内存限制:1000K
提交次数:1610 通过次数:656
题型: 编程题 语言: C++;C;VC;JAVA
Description
设集合R={r1,r2,...,rn}是要进行排列的n个元素,其中r1,r2,...,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。
输入格式
第1行是元素个数n,1<=n<=15。接下来的1行是待排列的n个元素,元素中间不要加空格。
输出格式
程序运行结束时,将计算输出n个元素的所有不同排列。最后1行中的数是排列总数。 (说明: 此题,所有计算出的排列原本是无所谓顺序的。但为了容易评判,输出结果必须唯一! 现做约定:所有排列的输出顺序如课本例2-4的程序段的输出顺序,区别仅是这道题是含重复元素。)
输入样例
4 aacc
输出样例
aacc acac acca caac caca ccaa 6
提示
课本上有“递归”实现无重复元素全排列的源程序。
稍加修改即可满足此题要求。
在递归产生全排列的那段程序开始之前,
加一个判断:判断第i个元素是否在list[k,i-1]中出现过。
Permpp(char list[], int k, int m)
{
......
for (int i=k; i<=m; i++)
{
if (Findsame(list,k,i))//判断第i个元素是否在list[k,i-1]中出现过
continue;
Swap (list[k], list[i]);
Permpp(list, k+1, m);
Swap (list[k], list[i]);
}
}
*/
mycode:
#include <iostream>
using namespace std;
int n,num=0;
char a[100];
void Perm(int k){
if(k>n-1){ //第n层 下标为n-1
for(int i=0;i<n;i++){
cout<<a[i];
}
num++;
cout << endl;
}else{
for(int i=k;i<n;i++){ //从k到n-1 选取字符作为前缀
int flag =0; //判断第i个元素是否在list[k,i-1]中出现过。
for(int j=k;j<i;j++){
if(a[j]==a[i]){
flag=1;
break;
}
}
if(flag) continue;
swap(a[i],a[k]); //作为前缀
Perm(k+1); // 错误示范perm(k++)
swap(a[i],a[k]); //复原顺序
}
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
cin >>a[i];
Perm(0);
cout << num<< endl;
return 0;
}
相关推荐
华农8594有重复元素的排列问题
设集合R={r1,r2,...,rn}是要进行排列的n个元素,其中r1,r2,...,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。
输入格式 第1行是元素个数n,1。...现做约定:所有排列的输出顺序如课本P11的例2-4的程序段的输出顺序,区别仅是这道题是含重复元素。) 输入样例 4 aacc 输出样例 aacc acac acca caac caca ccaa 6
设集合R={r1,r2,...,rn}是要进行排列的n个元素,其中r1,r2,...,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。 输入样例 4 aacc ...
问题描述:设R={r1,r2,…,rn}是要进行排列的个元素。其中元素r1,r2,…,rn 可能相同。试设计一个算法,列出R的所有不同排列。 ★算法设计:给定n及待排列的n个元素。计算出这n个元素的所有不同排列。 ★数据输入:由...
有重复元素的排列问题 Description 设R={ r , r , , rn 1 2 可能相同。试设计}是要进行排列的n个元素。其中元素n r , r , , r 1 2 一个算法,列出R的所有不同排列。 编程任务: 给定n 以及待排列的n 个元素...
实现2-5有重复元素的排列问题.cpp