Python递归实现全排列算法详解

本文分享了一个使用Python递归方式实现全排列的具体案例，供读者参考学习。

排列是指从n个不同元素中取出m个元素，并按特定顺序进行排列；当取出的元素个数m等于总元素个数n时，这种排列被称为全排列。

例如，集合{1, 2, 3}的所有全排列结果包括：{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 2, 1}以及{3, 1, 2}。

该算法的核心在于递归思想。

具体策略是：将数组中的第一个元素与最后一个元素进行交换（即a[1]与a[n]交换），然后对剩余部分a[n-1]递归求解全排列。

递归基例与步骤如下： 1）若数组仅含一个元素（n=1），如a={1}，则其全排列仅为{1}。 2）若数组包含两个元素（n=2），如a={1, 2}，则全排列包括： - {2, 1}：通过交换a[1]与a[2]得到，随后求a[2-1]={2}的全排列，归结为情况1）。 - {1, 2}：通过交换a[2]与a[2]（即不变）得到，随后求a[2-1]={1}的全排列，同样归结为情况1）。 3）若数组包含三个元素（n=3），如a={1, 2, 3}，则全排列包括： - {{2, 3}, 1}：交换a[1]与a[3]后，求a[3-1]={2, 3}的全排列，归结为情况2）。 - {{1, 3}, 2}：交换a[2]与a[3]后，求a[3-1]={1, 3}的全排列，归结为情况2）。 - {{1, 2}, 3}：交换a[3]与a[3]后，求a[3-1]={1, 2}的全排列，归结为情况2）。 ...

上述逻辑可依次类推至更多元素的情况。

以下是利用Python实现全排列的具体代码，文件名为perm.py：

COUNT=0
def perm(n,begin,end):
  global COUNT
  if begin>=end:
    print n
    COUNT +=1
  else:
    i=begin
    for num in range(begin,end):
      n[num],n[i]=n[i],n[num]
      perm(n,begin+1,end)
      n[num],n[i]=n[i],n[num]
 
n=[1,2,3,4]
perm(n,0,len(n))
print COUNT

程序最终输出的运行结果如下：

======================== RESTART: D:/Python27/perm.py ========================
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]
24
>>> 

以上就是本文的全部内容，希望能为读者的学习提供有益帮助，同时也欢迎大家继续支持本站。