UVa 10098 Generating Fast

2014.2.13更新：
這題使用STL_next_permunation即可，不過效率較慢，1.035秒，底下自幹的方法0.119秒。

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	int n;
	string str;
	cin >> n;
	while (n--){
	cin >> str;
	sort(str.begin(), str.end());
	do{
	for (char &c : str) // c++11 new standard：用來走遍所有元素
	cout << c;
	cout << endl;
	} while (next_permutation(str.begin(), str.end()));
	cout << endl;
	}
	}

view raw [UVa] 10098-2 Generating Fast.cpp hosted with ❤ by GitHub

想法：

char str[]存原本所有的字元

char temp[]來存已選擇的字元

bool choosed[]來表示哪些字元已被選擇

int all表示總共幾個字元

int left表示剩下幾個字元還沒選到

舉例子解釋，本題比如是"abc"，那麼第一個位置可能放a或b或c

所以在遞迴第一層用for loop從i=0~i=2。

假設現在i=1 將'b'放入temp

同時將choosed[1]標記為1  

那麼進入下一層遞迴就不會選到'b'

進入下層遞迴後 一樣for loop從i=0~2

但是'b'因為choosed[1]=1就不會選到

以此類推，例如現在第二層遞迴i=0選'a'

就將'a'放入temp(此時temp[]="ba")，choosed[0]=1;

再進入第三層時因為其他choosed皆=1，

所以只剩'c'，將'c'放入temp，

最後進入第四層因為left==0(所有字元都被選到了)，就可以print結果

返回第三層，將'c'從temp剔除，choosed[2]=0，此時i值已經到底了(i==2)

然後返回第二層，將'a'剔除，choosed[0]=0，此時i++，

到i==2時，把'c'放入temp(此時temp[]="bc")，進入第三層

之後以此類推。

從以上可寫成遞迴式:

permu(all,left,str,choosed,temp)
{
   if(left==0) printf結果;
   else{
      for(int i=0;i<all;i++){
         if(choosed[i]==0){
            choosed[i]=1;
            temp.push_back(str[i]);

            permu(all,left-1,str,choosed,temp);

            temp.pop_back();
            chooses[i]=0;
         }
      }
   }
}


注意： "aab" 會重複排列字元的問題，加入一條判斷式避免
if(choosed[i]==0 && choosed[i+1]==1 && str[i]==str[i+1]) continue;

	#include <cstdio>
	#include <algorithm>
	#include <string.h>
	#include <vector>
	using namespace std;
	void permu(int all,int left,char str[],bool choosed[],vector<char> &temp);
	bool cmp(char a,char b){
	return a<b;
	}
	/*
	temp[]來存已選擇的字元
	choosed[]來表示哪些字元已被選擇
	all表示總共幾個字元
	left表示剩下幾個字元還沒選到
	*/
	int main()
	{
	int n;
	char str[15];
	scanf("%d",&n);
	while(n--){
	scanf("%s",str);
	sort(str,str+strlen(str),cmp);
	bool choosed[15]={0};
	vector<char> temp;
	permu(strlen(str),strlen(str),str,choosed,temp);
	printf("\n");
	}
	return 0;
	}
	void permu(int all,int left,char str[],bool choosed[],vector<char> &temp)
	{
	if(left==0){
	for(int i=0;i<all;i++)
	printf("%c",temp[i]);
	printf("\n");
	}
	else{
	for(int i=0;i<all;i++){
	//避免aab會重複的問題
	if(choosed[i]==0 && choosed[i+1]==1 && str[i]==str[i+1]) continue;
	if(choosed[i]==0){
	choosed[i]=1;
	temp.push_back(str[i]);
	permu(all,left-1,str,choosed,temp);
	temp.pop_back();
	choosed[i]=0;
	}
	}
	}
	}

view raw [UVa] 10098 Generating Fast.cpp hosted with ❤ by GitHub