全排列

给定一个数组，请写一个算法来求取该数组的全排列。

1. dfs

private static void permutation(int[] src)
{
    StringBuilder res = new StringBuilder();
    boolean[] visited = new boolean[src.length];
    permute(src, visited, res);
}
/**
 * Use dfs to make it
 */
private static void permute(int[] src, boolean[] visited, StringBuilder res)
{
    if (res.length() == src.length)
    {
        System.out.println(res.toString());
        return;
    }
    for (int i = 0; i < src.length; ++i)
    {
        if (!visited[i])
        {
            visited[i] = true;
            res.append(src[i]);
            permute(src, visited, res);
            visited[i] = false;
            res.deleteCharAt(res.length() - 1);
        }
    }
}

2. 交换法

将第一个元素不断地与后面的元素交换，代表了以不同元素开头的情况。然后递归的对后面的元素进行同样的处理。

每次递归结束后，再将元素换回来(回溯):

/**
 * With an array [beg, end)
 * Switch the first element with each latter elements.
 * Then recursively handle with [beg + 1, end)
 * Notice: 
 * Though it may change the array's order during the process.
 * The array will come back to the initial condition after the excution done
 * @prama beg: 从哪里开始全排列
 */
private static void permuteBySwitch(int[] src, int beg)
{
    //边际条件，只有一个元素
    if (beg + 1 == src.length)
    {
        for (int i : src)
            System.out.print(i + " ");
        System.out.println();
    }
    //注意要从beg开始
    for (int i = beg; i < src.length; ++i)
    {
        //试探
        swap(src, beg, i);
        permuteBySwitch(src, beg + 1);
        //回溯
        swap(src, beg, i);
    }
}

以几个例子来说明。

---

以 [1, 2] 为例

1. 以1为首元素(即与自己交换)
   只有一个 [1, 2]，返回

2. 交换1和2，代表了以2为第一个元素的情况
   得到 [2, 1]

---

以 [1, 2, 3] 为例:

1. 以1为首元(交换自己)
   2. 后面的部分是 [2, 3]
   3. 同第一个例子，依次得到 [1, 2, 3] 和[1, 3, 2]
   4. 交换回来(还是1和1换)，返回初始的 [1, 2, 3]
2. 把1和2交换得到 [2, 1, 3]
   1. 处理 [1, 3] 部分
      1. 1和1交换，然后到达了边界处，输出 [2, 1, 3]，返回
      2. 1和3交换，到达边界处，输出 [2, 3, 1]。返回后将1和3换回来，回到了刚才 [2, 1, 3] 的情况
   2. [1, 3] 处理完，返回到最开始的 [2, 1, 3] 处，将1和2还回来。
3. 继续交换1和3，做同样的处理。