递归算法求n个数字的全排列_递归算法求n个数字的全排列

(请花几分钟细细阅读，可以的话拿出你的小本本画一画)

全排列

定义：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列。

公式：全排列数f(n)=n!(定义0!=1)

其想法是将第k个元素与后面的每个元素进行交换，求出其全排列。这种算法比较节省空间。

全排列的基本思想是：
把待全排列记录分为两个部分：
（1） 第一个记录
（2） 剩下的所有元素

我们先从一个小例子开始

int arr[] = { 1, 2, 3 };

int k = 0;

第一次：k=0，下标0与1和2交换，新产生2种。

第二次：k=1，现在加上数组本身就已经有3种情况了，在这个基础之上再与下标1与2交换，新产生3种。

综上，完成数组arr的6种排列。

所以很明显，这就是一个递归的思想：给你部分记录，全排列就是所有可能出现在第一个位置的记录与剩下的元素的全排列，剩下的元素的全排列又是剩下的可能出现在第一个位置的元素与剩下的元素的全排列，依次重复下去。

注：如果实在理解不到，那就先把代码记在脑海里，比赛能写出来也是你自己的能力。

(项目实战)

标题：考考你

请输出123所有的全排列。

有了上面的知识，做这种题简直如鱼得水。

public class demo4 {
	/**
	 * @param arr     待排数组
	 * @param index 前缀的位置(数组下标)
	 */
	public static void fun1(char arr[], int index) {
		// 递归终止条件，index每次加1
		if (index == arr.length - 1) { // 也可以arr.length
			System.out.println(String.valueOf(arr));// 打印
			return;
		}

		for (int i = index; i < arr.length; i++) {
			{
				char t = arr[index];
				arr[index] = arr[i];
				arr[i] = t;
			}
			fun1(arr, index + 1);
			{
				char t = arr[index];
				arr[index] = arr[i];
				arr[i] = t;
			}
		}
	}

	public static void main(String[] args) {
		String str = "123";
		fun1(str.toCharArray(), 0);
	}
}

输出

123
132
213
231
321
312

详解

分两个步骤： 
（1）确定第一位的字符 
数组arr从index从0开始到arr.length-1的所有记录都可以出现在第一个位置，所以直接一个for循环，考虑了这所有的情况。在for循环中，交换方法就是交换index和i位置的数，保证当前i指向的记录出现在第一个位置，也就是index指向的位置。
（2）剩下的记录继续做全排列 
这个就是一个递归函数的调用，只需要修改起始位置，也就是index+1，因为start的位置已经放了记录，所以只需要继续做从index+1到arr.length-1的全排列即可。

递归的终止条件就是当index==arr.length-1，也就是只有一个记录需要做全排列，也就是到了最后一个记录，这就是全排列的一种情况，输入本次的记录，也就是数组arr即可。

特别鸣谢

一次性弄懂到底什么叫做全排列（递归算法）（例题+源代码讲解）

一次性弄懂到底什么叫做全排列（递归算法）（例题+源代码讲解）

https://baike.baidu.com/item/全排列/4022220?fr=aladdin#4

今天的文章递归算法求n个数字的全排列_递归算法求n个数字的全排列分享到此就结束了，感谢您的阅读。