全排列的递归实现

突然想手写下这算法，递归实现并不复杂，主要是要想明白2件事情：（以对’xyz’进行全排列为例）

xyz的全排列记为p(xyz)，等于：

     x + p(yz)
           y + p(z)  => xyz
           z + p(y)  => xzy
    
     y + p(xz)
           x + p(z)  => yxz
           z + p(x)  => yzx
    
     z + p(yx)
           y + p(x)  => zyx
           x + p(y)  => zxy

如何控制每一次计算时被单独提出来的字符？比如算好了x + p(yz)后，接下来应该计算y + p(xz)了，这里实际是相当于x与y进行了一次交换，并且算好y + p(xz)了要还原到xyz的状态，进而让x与z交换，以计算z + p(yx)

手写Java代码如下：

class Permutation{
	public static void main(String[] args){
		char[] chars = {'x', 'y', 'z'};
		permutation(chars, 0, chars.length);
	}


	private static void permutation(char[] chars, int start, int end){
		if(start == end){
			System.out.println(new String(chars));
		}else{
			for(int i = start; i < end; i++) {
				swap(chars, i, start);
				permutation(chars, start + 1, end);
				swap(chars, i, start);
			}
		}
	}

	private static void swap(char[] chars, int i, int j){
		char t = chars[i];
		chars[i] = chars[j];
		chars[j] = t;
	}
}

记录

全排列的递归实现

Search

Table of Contents