2022年 11月 9日

python 实现全排列

全排列一般用递归来写最为方便，也有非递归版本，这里只记一下递归的方法。

比如要求 1、2、3、4的全排列，一共是4!=24种，那么就可以认为是  1+P(2、3、4）;2+P(1,3,4) ;3+P(1,2,4); 4+p(1,2,3);

而三个数字的排列又可以递归为  a+P(b,c), 直到 只有一个数的时候P(x)直接返回x。

具体代码如下：

  1. def permutation(array):
  2.     s = []
  3.     if len(array) == 1:
  4.         return [array]
  5.     else:
  6.         for i in range(len(array)):
  7.             array[i], array[0] = array[0], array[i]   #每次交换一个元素
  8.             temp = permutation(array[1:])   #递归
  9.             for l in temp:      #如果只是打印不用保存，那么for循环可以去掉
  10.                 s.append([array[0]]+l)
  11.             array[i], array[0] = array[0], array[i]   #恢复原始序列
  12.     return s

测试：

  1.     test = [i for i in range(4)]
  2.     print(permutation(test))
  3.  
  4. ---------------------------------------------------------------------------------
  5. [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 2, 1], [0, 3, 1, 2], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 2, 0], [1, 3, 0, 2], [2, 1, 0, 3], [2, 1, 3, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 3, 0, 1], [2, 3, 1, 0], [3, 1, 2, 0], [3, 1, 0, 2], [3, 2, 1, 0], [3, 2, 0, 1], [3, 0, 2, 1], [3, 0, 1, 2]]