面试题:排列组合问题

老鼠盘根 发布于 2014/03/05 09:35
阅读 601
收藏 0
一个面试题:如何列出由5个不同字符组成的长度为5的所有字符串排列组合,而且字符串里要用到所有的这5个字符.延伸一下可以将5改为n
加载中
1
Timco
Timco
刚写了,明天答。
1
云香水识
云香水识
function charsMap(o){
 o = (o+"").replace(/\s+/g,"");
 switch(o.length){
 case 0: 
 case 1: return [o];
 default: 
 var p = /^(\S+?)(\S)$/.exec(o), 
 _r = charsMap(p[1]), 
 l = p[2], 
 r = [];
 
 for (var i = 0; i < _r.length; i++) {
 var t = _r[i];
 for (var j = 0, len = t.length; j <= len; j++) {
 r.push( t.replace( new RegExp("^(\\S{"+j+"})(\\S{"+(len-j)+"})$"), "$1"+l+"$2" ) );
 }
 }
 return r;
 }
}


var arr = "abcde";
var result = charsMap(arr).sort();


console.log( result );


0
巴顿
巴顿

如果是a,b,c,d,e就列出

abcde acdeb .....

bacde ......

c......

d...

e.....

这样?






老鼠盘根
老鼠盘根
恩呢,就是这个意思. n=5 应该是120种 5*4*3*2*1 要程序实现
0
Jeky
Jeky
def permutate(cur, l):
	if cur:
		print cur

	for elem in l:
		newL = [e for e in l if e != elem]
		permutate(cur + elem, newL)


permutate('', ['a', 'b', 'c', 'd', 'e'])



0
温佐镜
温佐镜

思路:当字符串长度是很小时,完全用嵌套循环可实现;但长度很长时,套循环显然是不行的,只能借助递归

public static void main(String[] args) {

		String str = "abcde";

		combi(str, "");

	}

	private static void combi(String str, String result) {

		if (str.length() == 0) {
			System.out.println(result);
			return;
		}

		for (int i = 0; i < str.length(); i++) {
			String str2 = str.substring(0, i) + str.substring(i + 1);
			combi(str2, result + str.charAt(i));
		}

	}




0
Shazi199
Shazi199
import java.util.LinkedList;

public class GenerateString {

	private String string;

	public GenerateString(String letters) {
		this.string = letters;
	}

	public void print() {
		LinkedList<String> letters = spilitString();
		exchange(letters, letters.size());
	}

	public void exchange(LinkedList<String> letters, int n) {
		if (n > 2) {
			exchange(letters, n - 1);
		} else if (n == 2) {
			getListString(letters);
		}
		for (int i = 0; i < n - 1; i++) {
			LinkedList<String> temp = new LinkedList<String>();
			for (int j = 0; j < n; j++) {
				temp.add(letters.pollLast());
			}
			for (int j = 0; j < n; j++) {
				letters.add(temp.pollFirst());
			}
			if (n > 2) {
				exchange(letters, n - 1);
			} else if (n == 2) {
				getListString(letters);
			}
		}
	}

	public void getListString(LinkedList<String> letters) {
		for (int i = 0; i < letters.size(); i++) {
			System.out.print(letters.get(i));
		}
		System.out.println();
	}

	public LinkedList<String> spilitString() {
		LinkedList<String> letters = new LinkedList<String>();
		for (int i = 0; i < string.length(); i++) {
			letters.add(string.substring(i, i + 1));
		}
		return letters;
	}

	public static void main(String[] args) {
		GenerateString g = new GenerateString("abcde");
		g.print();
	}
}

利用递归和栈/队列实现

0
qiuyukuhe
qiuyukuhe
为什么这么复杂。说到底就是非重复随机数的问题
0
ooz
ooz
programming erlang中变位词的例子
perms([]) -> [[]];
perms(L) -> [[H|T] || H<-L, T<-perms(L--[H])].
返回顶部
顶部