10098 - Generating Fast

/*
生成可重集的排列，详解见刘汝佳p118
题意：输出字符串的全排列，输出时由小到大排序
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[15];
void print_permutation(int n,int *A,int cur)
	//递归技巧：传递一数组过来存储已确定的前缀（***）
{
	int i,j;
	if(cur==n)
	{
		for(i=0;i<n;i++)
			printf("%c",A[i]);
		printf("\n");
	}
	else for(i=0;i<n;i++)
		if(!i || str[i]!=str[i-1])//保证重复的字符只选一次
	{
		int c1=0,c2=0;
		for(j=0;j<cur;j++) if(str[i]==A[j]) c1++;
		for(j=0;j<n;j++) if(str[i]==str[j]) c2++;
		if(c1<c2)
		{
			A[cur]=str[i];
			print_permutation(n,A,cur+1);
		}
	}
}
int main()
{
	//freopen("data.in","r",stdin);
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int A[15];
		scanf("%s",str);
		int len=strlen(str);
		sort(str,str+len);
		print_permutation(len,A,0);
		printf("\n");
	}
	return 0;
}

STL解法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		char str[15];
		scanf("%s",str);
		int len=strlen(str);
		sort(str,str+len);
		do
		{
			printf("%s\n",str);
		}while(next_permutation(str,str+len));
		printf("\n");
	}
	return 0;
}