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
你的代码，效率很差，而且与楼主的算法一样，能不能再提出其他的算法？？？  回复  更多评论
  

这类问题一般都是用递归来解
不知道有没有高手，可以使用非递归的方式求解问题  回复  更多评论