如何用Python代码实现基于回溯的深度优先搜索全排列算法？

本文共计1098个文字，预计阅读时间需要5分钟。

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

公式：全排列数f(n)=n!（n的阶乘）

当m=n时，所得到的排列情况称为全排列。

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

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

1 递归实现全排列（回溯思想）

1.1 思想

举个例子，比如你要对a,b,c三个字符进行全排列，那么它的全排列有abc,acb,bac,bca,cba,cab这六种可能就是当指针指向第一个元素a时，它可以是其本身a(即和自己进行交换)，还可以和b，c进行交换，故有3种可能，当第一个元素a确定以后，指针移向第二位置，第二个位置可以和其本身b及其后的元素c进行交换，又可以形成两种排列，当指针指向第三个元素c的时候，这个时候其后没有元素了，此时，则确定了一组排列，输出。但是每次输出后要把数组恢复为原来的样子。