private static List<String> overall(String str){
List<String> strs = new ArrayList<String>();
for(int i=0;i<str.length();i++){
List<String> subStrings = overall(str.substring(0,i)+str.substring(i+1));
for(String s : subStrings){
strs.add(str.substring(i,i+1)+s);
}
}
if(str.length()==1){
strs.add(str);
}
return strs;
}  回復  更多評論
  

if the input string contains the redundant char, for example: "aaaa"?
  回復  更多評論
  

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.lang.time.StopWatch;

/*
* @(#)PermutationAndCombination.java 2010-3-23
*
* @COPYRIGHT@
*/

/**
* <p>
* 排列組合
* </p>
*
* @version 1.0
* @author Lancelot
*
*/
public class PermutationAndCombination {

private char[] resource = new char[0];

private List resultBuffer = new ArrayList();

public PermutationAndCombination() {}

public PermutationAndCombination(char[] resource) {

this.resource = resource;
}

public PermutationAndCombination(String resource) {

this.resource = resource.toCharArray();
}

public List process() {

for(int i = 0, num = resource.length; i < num; i++) {

char[] part = ArrayUtils.subarray(resource, i, i + 1);
char[] tmpResource = ArrayUtils.remove(resource, i);
permutation(tmpResource, part);
}

return resultBuffer;
}

private void permutation(char[] resource, char[] prefix) {

int num = resource.length;
if( 1 == num ) {

char[] result = ArrayUtils.addAll(prefix, resource);

System.out.println(String.valueOf(result));

//下面的代碼可以解決重復結果的問題——比如傳入了aaaa/ aaba這樣的字符串，但效率會稍差。
/*String resultString = String.valueOf(result);
if( !resultBuffer.contains(resultString) ) {
resultBuffer.add(resultString);
}*/
} else {

for(int i = 0; i < num; i++) {

char[] result = ArrayUtils.add(prefix, resource[i]);

permutation(ArrayUtils.remove(resource, i), result);
}
}
}

public static void main(String[] args) {

StopWatch clock = new StopWatch();
clock.start();
System.out.println(new PermutationAndCombination("abcdefge").process());
clock.stop();
System.out.println("clock.getTime() => " + clock.getTime());
}
}

這段代碼可在1.3/ 1.4的環境下運行，而且在效率與博主的代碼相差無幾的情況下，可讀性要更好。
  回復  更多評論
  

太 厲害了，看了半天才看懂，樓主對遞歸很熟，佩服佩服，有空教教我  回復  更多評論
  

你的算法前提是，字符串沒有重復字符。  回復  更多評論
  

我寫了個更清晰的算法
只用了核心代碼3部完成全排列遞歸
recurrence;
/*
* ：輸入一個字符串，顯示出字符串的所有排列。例如：輸入"abc"，就得輸出"abc"、"acb"、"bac"、"bca"、"cab"、"cba" 所有可能的序列。
*
* */
public class QuanPaiLie {

public void swap(char[] array,int i,int j){
char temp = array[i];
array[i] = array[j];
array[j]=temp;
}

public void compute(char[] array, int pos){
if(pos == array.length){
for(char ch:array){
System.out.print(ch);
}
System.out.println();
}
for(int i=pos;i<array.length;i++){
swap(array, i, pos);
compute(array,pos+1);
swap(array, pos, i);
}

}


public static void main(String[] args) {
String input = "abc";
char[] c = input.toCharArray();
new QuanPaiLie().compute(c,0);
}

}
  回復  更多評論
  

@Gauss Reborn
你的代碼，效率很差，而且與樓主的算法一樣，能不能再提出其他的算法？？？  回復  更多評論
  

這類問題一般都是用遞歸來解
不知道有沒有高手，可以使用非遞歸的方式求解問題  回復  更多評論