網頁

2013年12月30日 星期一

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;