# 数字全排列

## 问题描述

给一个不重复的数字数组，写一个程序，输出全排列。

比如给定数组：

```
[1, 2, 3]
```

输出：

```
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
```

## 解决思路

这个问题很经典，接下来尝试使用数学归纳法的思想来解决这个问题。

在中学的时候，我们就知道一个长度为n的数列有n!个排列。因为第一个数字有n种情况，第二个数字有n-1种情况，第三个数字有n-2种情况……第n个数字只有一种情况了，用公式表示就是n\*(n-1)\*(n-2)….\*1 = n!

我们换一个思维来考虑，以数组\[1,2,3]为例，它的全排列为：

* 第一个数字为1的其他两个数字的全排列 + 第一个数字为2的其他两个数字的全排列 + 第一个数字为3的其他两个数字的全排列。
* 那么两个数字的全排列怎么算呢，以\[1,2]为例，就是：

  第一个数字为1的剩下的数的全排列 + 第一个数字为2的剩下的数的全排列。
* 因为剩下的只有一个数，就不用继续了，到这就可以输出了。

依次类推到n个数字的全排列：

* 设数组 p = {r1, r2, r3, r4, r5…., rn}，设p的全排列为perm(p)，设pn = p - {rn}。
* 那么perm(p) = { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }。
* 同样思路，也可以算出perm(p1), perm(p2), perm(p3)……perm(pn)。
* 继续，就可以使用递归求解了，递归的出口就是perm求的全排列数组里面只有一个值。

## 代码实现

下面是java的实现代码：

```java
import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        Test t = new Test();
        t.perm(arr, 0, arr.length);
    }

      //求数组全排列
    public void perm(int[] nums, int start, int len) {
        //判断递归出口，当start == len - 1时，也就是要做的全排列只有一个值 ，那么就可以输出了
        if(start == len - 1) {
            System.out.println(Arrays.toString(nums));
        }else {
            /*
             * 没有到递归出口时，这一段代码是关键
             * for循环模拟的是：
             * { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }
             * 从r1, r2, r3 一直到 rn 作为第一位，求剩下的全排列
             */
            for(int i = start; i < len; i++) {
                swap(nums, start, i);//通过交换，依次将每个数放在第一位
                perm(nums, start + 1, len);//递归调用
                swap(nums, start, i);//交换回来，保证原数组不会变，以进行下一轮全排列
            }
        }
    }

    //交换数组中的两个值
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}
```

输出结果：

```
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
```

> 参考：
>
> <http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html>
>
> <https://blog.csdn.net/randyjiawenjie/article/details/6313729>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/shu-zi-quan-pai-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.