经典递归问题：全排列问题

image

【题目】设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。

【算法讲解】：

设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。
R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

<font color="blue" face="方正宋黑简体">实现思想：将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。</font>

---

【示例】

当n=3，并且E={a，b，c}，则：
perm(E)=a.perm({b,c}) + b.perm({a,c}) + c.perm({a,b})
perm({b,c})=b.perm(c) + c.perm(b)
a.perm({b,c})=a.b.perm(c) + a.c.perm(b)
​ =a.b.c + a.c.b=(abc, acb)

我的代码：

public class Main {
    public static void main(String[] args){
        char[] data="ABC".toCharArray();
        f(data,0);
    }
    private static void f(char[] data,int k) {
        if(k==data.length){//只剩下一个元素
            for(int i=0;i<data.length;i++){
                System.out.print(data[i]+" ");
            }
            System.out.println();
        }
        for(int i=k;i<data.length;i++){
            {char c=data[k];data[k]=data[i];data[i]=c;}//试探
            f(data,k+1);
            {char c=data[k];data[k]=data[i];data[i]=c;}//回溯
        }
    }
}

关于回溯：

3个电灯串联在一起，其中有个灯泡坏了，通过在灯泡正负极接上一根导线的方法来筛选出坏了的灯泡，每次检测下一灯泡时，必须先将连在上一灯泡的导线取下，保持在最初状态，这就是回溯。

image