UVa 10098 Generating Fast

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




想法：

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;