算法：输出一串字符的全排列

package test;

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

public class Test {

	public static void main(String[] args) {
		String str = "abcdef";
		List<String> list = new Test().completeArray(str, 0);
		
		System.out.println(list);
		System.out.println("there are " + list.size() + " kinds of groups.");
	}

	public List<String> completeArray(String str, int index) {
		if (index == str.length() - 1) {
			List<String> list = new ArrayList<String>();
			list.add(String.valueOf(str.charAt(index)));
			return list;
		}
		
		List<String> newLists = new ArrayList<String>();
		List<String> oldLists = completeArray(str, index + 1);
		
		for (String oldString : oldLists) {
			char c = str.charAt(index);
			for (int i = 0; i <= oldString.length(); i++) {
				newLists.add(Insert2Str(oldString, i, c));
			}
		}
		return newLists;
	}

	private String Insert2Str(String str, int i, char c) {
		if(str == null){
			return String.valueOf(c);
		}else {
			return str.substring(0, i) + c + str.substring(i);
		}
	}
}

思路是递归，要取str的全排列，只要取后n-1位的全排列，再把第1位往里面插入，就ok了。递归的终止是，游标index扫描到最后一位，只有一个字母的时候排列之后一种，开始return

产生新字符串那地方，刚开始的时候用ArrayList的add方法，但是这样的话有太多的转换类型操作，代码显得很乱，看着很不爽，就写了一个Insert2Str的方法，往字符换的指定位置插入一个字符。

代码存在效率问题，大概到8个字母以上运行就很慢了，10几位的话会报java.lang.OutOfMemoryError异常，求问题所在，和更好的算法

评论

5 楼 reilost 2010-05-28  

话说...10几位的放list里-.-怎么会不溢出...
12位就已经479001600了

4 楼 reilost 2010-05-28  

囧,某公司的笔试是数字还有限制条件...直接把代码改了下....

	public static StringBuilder sb = null;
	public static Set<String> resultSet = new HashSet<String>();

	public static void main(String args[]) {
		char a[] = "abcdef".toCharArray();
		build(a, 0, a.length);
	}

	public static void build(char[] arr, int k, int m) {
		if (k == m) {
			for (int i = 0; i < arr.length; i++) {
				if (sb == null)
					sb = new StringBuilder();
				sb.append(arr[i]);
			}
			resultSet.add(sb.toString());
			sb.delete(0, sb.length());
		} else {
			for (int i = k; i < m; i++) {
				swap(arr, k, i);
				build(arr, k + 1, m);
				swap(arr, k, i);
			}
		}
	}
	public static void swap(char[] arr, int i, int j) {
		char tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;

	}

3 楼 cjjer 2010-05-27  

        static List<string> GetString(string x)
        {
            List<string> ls = new List<string>();
            if (x.Length.Equals(1))
            {
                ls.Add(x);
            }
            else
            {
                string z = x;
                foreach (char i in x)
                {
                    foreach (string si in GetString(z.Replace(i.ToString(), "")))
                    {
                        ls.Add(i.ToString() + si);
                    }

                }
            }
            return ls;
        }


前几天写的。
是c#的，顺手贴。

超过11位也算起来就慢的很。

11 All.Count 3628800 int
这个差不多5秒左右了。

2 楼 raito_yagami 2010-05-27  

能描述一下问题么？

1 楼 liuzhiqiangruc 2010-05-26  

关注学习。。。