上星期大學時認識的一個學弟問了一個問題
一個我在高中時用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數量往往會超過這個限制
知其然而知其所以然果然是很重要的
留言列表
