上星期大學時認識的一個學弟問了一個問題
一個我在高中時用Quick Basic 4.5做過不少次的題目
輸入任意字串然後顯示出它所有可能的排列組合
那時一開始用的是很菜的做法 - 巢狀迴圈 
用C++寫就簡單很多了   因為有好用的STL
 
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
void main(void){
                          string str;
                          cin>>str;
                          while(next_permutation(str.begin(),str.end()))
                                                      cout<<str<<endl;
}
 
真是有夠簡單扼要的
不過學弟他們需要的是要用Java寫   而且還要用遞迴的技巧
 
import java.io.*;
public class Permutation {
         private static int n=0;
         private static String[] StringList;

         private static int fraction(int y)
         {

                   int i,ans;
                   ans=1;
                   for (i=1;i<=y;i=i+1)
                   {
                           ans=ans*i;
                   }
                   return(ans);
         }

         public static String[] perm(char[] num)
         {
                  StringList=new String[fraction(num.length)];
                  for(int i=0;i<StringList.length;i++)
                            StringList[i]="";
                  perm(num,0);
                  return StringList;
         }

         private static void perm(char[] num, int i) {
                  if(i < num.length - 1) {
                       for(int j = i; j <= num.length - 1; j++) {
                              char tmp = num[j];
 
                              for(int k = j; k > i; k--)
                                        num[k] = num[k-1];
                              num[i] = tmp;
                              perm(num, i+1);
                              for(int k = i; k < j; k++)
                                        num[k] = num[k+1];
                              num[j] = tmp;
                      }
                 }
                 else
                { 
                              for(int j = 0; j < num.length; j++)
                                       StringList[n]+=num[j];
                              n++;
                }
          }

          public static void main(String[] args)throws IOException{
                   System.out.print("=>");
                   BufferedReader Buf=new BufferedReader(new InputStreamReader(System.in));
                   String input=Buf.readLine();
                   char[] num=input.toCharArray();
                   String[] ans=perm(num);

                   for(int i=0;i<ans.length;i++)
                             System.out.println(ans[i]);
          }
}

 
不知道Java的collection framework有沒有類似像STL的方法
使用遞迴有很多時候不會是最好的做法....   消耗不少記憶體
 
原本在研一做的一個小作業也是利用遞迴的技巧找影像中Connected Component
但是到了研二實際在使用的時候就完全不可行了
因為遞迴的深度是有限制的...   而實際影像的區塊pixel數量往往會超過這個限制
知其然而知其所以然果然是很重要的
arrow
arrow
    全站熱搜

    志 發表在 痞客邦 留言(0) 人氣()