求字符串的全排列

问题描述：求一个序列的所有排列情况。

算法思路：使用递归的思想。将每个元素放到长度为n的序列的第一个，然后对剩余的元素进行全排列。

参数说明：in表示输入的字符串，out用来存放输出的字符串，length表示字符串长度，used用来标记哪些字符已经被使用，level用来表示递归的深度。注意，当递归返回时，要将used相应项恢复。

 

void permute(char[] in, char[] out, int length, int[] used, int level) {
    if (level == length) {
        System.out.println(out);
        return;
    }
		
    for (int i = 0; i < length; i++) {
        if (used[i] == 0) {
	    out[level] = in[i];
	    used[i] = 1;
	    permute(in, out, length, used, level+1);
	    used[i] = 0;
        }	
    }
}

 

也可通过swap直接在原始序列中进行元素交换，在递归返回后，也需要通过swap恢复元素原来的位置。

 

void permute(char[] in, int level, int length) {
   if (level == length) {
        print(in)
        return;
    }
		
    for (int i = level; i < length; i++) {
        swap(in[level], in[i]);
        permute(in, level+1, length);
        swap(in[level], in[i];
    }
}