Time Limit: 10 second
Memory Limit: 2 MB
问题描述
设r={r1,r2,...,rn}是要进行排列的n个元素，其中r1,r2,...,rn可能相同。给定 n以及待排列的n个元素，设计一个算法，求出这n个元素的所有不同排列。
Input
第一行是元素个数n，1≤n≤500，接下来第二行起(即有可能不同行）是待排列的n个元素。
Output
n个元素的所有不同排列（按字典顺序依次输出），最后一行中的数是排列总数
Sample Input
4 aacc
Sample Output
aacc acac acca caac caca ccaa 6
Sample Input1
16 cccc cccc cccc cccc
Sample Output1
cccccccccccccccc 1
【题解】
首先把字符读入，要用( while cin >> str != eof ),这样可以一直读到文件结束。
读完之后将读入的东西村在字符串中，扫描一下各个字母出现的次数，用a[1..26]来代表26个字母出现的个数。
搜索的策略是，for i =1 to 26 ,如果a[i] > 0，则用i这个字母来进行组合。
如aacc;
a[1] = 2;a[3] =2;
先是看到a[1] > 0，先用掉一个当前字符串变成“a”，然后让a[1]递减。
再扫描的时候又看到了a[1] == 1 >0,再用a，然后字符串变成"aa",这时候a[1] 变成0了，
再扫描 遇到a[3] >0，再加一个c进去，字符串变成“aac”,a[3]--,再扫描，仍然是a[3]>0,再用一次，a[3]==0,这时字符串变成“aacc”,输出。
然后搜索退一层，a[3] == 1,但是没有i > 3的a[i]满足a[i] >0 了，于是再退一层，a[3] == 2,这时字符串已经变成又变回“aa”了，这时的i刚搜完3，而a[4..26]没有大于0 的，
于是再退一层，字符串变成“a”这时a[1] = 1,a[3] =2,我们的i ==1 ，这时候 i再变成3，遇到a[3] == 2,加上一个c,字符串变成“ac”。。。。
以此类推。
可以看到，这样的搜索策略不会出现重复的情况，省去了判重的工作。
这个道题主要就是考的搜索策略。
【代码】
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
int n,num = 0,l,now = 0,a[27],ans[550],ta = 0;
string s,ts;
bool bo[550];
void input_data() //输入数据
{
scanf("%d",&n);
s= "";
while ( ( cin >> ts)) //用于输入不定行的字符串
s += ts; //把它们连接起来
l = s.size();//获取字符串的长度
for (int i = 1;i <= 26;i++)
a[i] = 0;
for (int i = 0;i <= l-1;i++) //统计各个字母出现的次数。
a[s[i]-'a'+1]++;
}
void sear_ch(int d)
{
ans[++now] = d; //记录下我们用的字母是什么 以int的形式存储
a[d]--; //用掉了 就要递减。
for (int i = 1;i <= 26;i++) //查找剩余的可用字母
if (a[i] > 0)
sear_ch(i);
if (now == l) //如果所有字母都用过了，就输出。
{
for (int i = 1;i <= now;i++)
putchar(ans[i]-1 +'a');
printf("
");
ta++; //方案数递增。
}
now--; //回溯。
a[d]++;
}
void get_ans()
{
for (int i = 1;i <= 26;i++) //如果某个字母还有剩余，就用它。
if (a[i] > 0)
sear_ch(i);
}
void output_ans()
{
printf("%d
",ta);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}