全排列算法及其python实现
1. 全排列算法
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
例如，我们要获取1,2,3,4的全排列，其构造过程如下：
首先固定1，找2,3,4的全排列 然后固定2，找1,3,4的全排列 然后固定3，找1,2,4的全排列 最后固定4，找1,2,3的全排列
显然这是一个递归的过程。每次固定完一个数字之后，需要将其与剩下的某个数字交换位置，然后对剩下数字求全排列。求完全排列之后，将数字位置换回来，继续与其他数字交换。
当且仅当递归到只有一个数字的全排列时，打印结果。
2. Python实现
计算1,2,3,4的全排列
# -*- coding: utf-8 -*-
def perm(ls, start, end):
if(start >= end):
print(ls)
else:
for i in range(start, end + 1):
ls[start], ls[i] = ls[i], ls[start]
perm(ls, start + 1, end)
ls[start], ls[i] = ls[i], ls[start]
def main():
ls = [1,2,3,4]
perm(ls, 0, 3)
if __name__ == "__main__":
main()
输出：
[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]