| 先来复习一下概率论的基础知识： 第 m 个位置有 n 种选法 |
如果我们要编程生成所有的排列，基本上都是嵌套循环
假如 list 有 n 个元素，从中选 2 个进行排列，伪代码基本如下
for j = 0 to list.length-1{
// 找到一种排列方法
temp = list[i,j]
// 根据情况排除重复
..}
问题是上面的例子，我们知道选 2 个元素排列，所以循环是 2 层。
但是，如果我们求得是 P(list,n)，n 并不确定，我们不知道循环是几层，要想写一个通用的函数，只能借鉴上面的思想，但是不能使用上面的形式
我的想法是：
1、用一个数组 repeat[] 来保存每层的循环变量：repeat[0] 保存第 0 层循环变量的位置，repeat[1] 保存第 1 层循环变量的位置......repeat[n-1] 保存第 n-1 层循环变量的位置
2、标记当前正在第几层循环：layer
3、集合长度已知 ：size = list.length
4、临时数组：
temp[]，长度为 n
3、算法描述如下：
循环体（layer == 0 且 repeat[0]== size 则退出循环）
{
如果（前 n-1 层）
{
取出该层循环变量：pos=repeat[layer]
如果 (pos 到达该层末尾，即 pos==size)
{
temp[layer]=null
repeat[layer]=0//该层循环变量归零
layer--//
回到上一层
continue
}
否则
{
temp[layer]=list[pos]
repeat_count[layer]++//
该层循环变量增加1
layer++//
层数增加 1
continue
}
否则（在最内层）
{
不停改变 temp 最后一个元素，每改变一次，就得到一种新的组合，该层循环变量增加1
当最内层也到达 List 末尾：将该层循环变量归零，回到上层
}
}
下面是我用 Python 编写的 permutation 函数，接受三个参数
第一个参数：如果数字则返回排列数；如果是集合，则返回排列的集合
第二个参数：选几个数排列，默认全排序
第三个参数：是否允许重复，默认不允许
例子：
print permutation( 10 , 2 ), ' \n ' # 10 选 2 排列数
print permutation( 10 ,duplicate = True), ' \n ' # 允许重复的全排列
li = [ ' a ' , ' b ' , ' c ' ]
print ' 全排列： ' ,permutation(li), ' \n '
print ' 选2 ： ' ,permutation(li, 2 ), ' \n '
print ' 允许重复 ： ' ,permutation(li,duplicate = True), ' \n '
运行结果：
下面给出源代码：
排列
本文转自左洸博客园博客，原文链接：http://www.cnblogs.com/myqiao/archive/2009/07/29/1533563.html，如需转载请自行联系原作者
# !/usr/bin/python
# -*- coding:GBK -*-
def permutation(arr,n = None,duplicate = False):
""" arr : 如果是数字，则返回全排列数；如果是数组，则返回全排列集合
n : 元素个数，默认全排列
duplicate: 同一个元素是否可以放在多个位置，默认不允许
注释:如果允许元素重复，n 个位置，每个位置 size 种选法，排列数 size ** n
"""
# 需要排列的数目，默认全排列
if (n == None):
if (type(arr) is int):n = arr
else :n = len(arr)
# 元素数目
if (type(arr) is int):size = arr
else :size = len(arr)
if (n < 1 ): raise Exception, ' Error: n < 1 '
if (n > size): raise Exception, ' Error: n > len(arr) '
# 第一个元素是数字，则返回全排列数目
if (type(arr) is int):
if (duplicate):
return size ** n
else :
result = size
temp = size - 1
while ((size - temp) < n):
result = result * temp
temp = temp - 1
return result
# 循环计数器，一层一个，共 n 个，都初始化为 0
repeat_count = [0 for i in range(0,n)]
# 当前正在循环的层
layer = 0
# 随着计数器和层数不停变化的临时组合,N 维数组
v_temp = [None for i in range(0,n)]
result = []
# 当前在第 0 层，且第 0 层计数器达到末尾时退出循环
while (repeat_count[0] < size) or (layer > 0):
if (layer < n - 1 ):
# 小于 n-1 层
pos = repeat_count[layer]
if (pos < size):
# 层计数器 < size ，保存层计数器指向的元素，计数器前进一位，增加一层
if ( not duplicate):
# 不允许重复
if ((pos + 1 ) in repeat_count):
# 检查到重复，计数器前进一位，继续
repeat_count[layer] = repeat_count[layer] + 1
continue
v_temp[layer] = arr[pos]
repeat_count[layer] = repeat_count[layer] + 1
layer = layer + 1
else :
# 否则，层计数器归零，向上一层
v_temp[layer] = None
repeat_count[layer] = 0
layer = layer - 1
else :
# 第 n-1 层：计数器每移动一个位置，都是一种组合
pos = repeat_count[layer]
if (pos < size):
if ( not duplicate):
# 不允许重复
if ((pos + 1 ) in repeat_count):
# 检查到重复，计数器前进一位，继续
repeat_count[layer] = repeat_count[layer] + 1
continue
v_temp[layer] = arr[pos]
# 找到一种组合，添加至结果集中
result.append([it for it in v_temp])
# 层计数器前进 1 位
repeat_count[layer] = repeat_count[layer] + 1
else :
# n-1 层计数器到达末尾，将层计数器归零 ，返回上层
repeat_count[layer] = 0
layer = layer - 1
return result
if __name__ == " __main__ " :
print permutation( 10 ), ' \n ' # 全排列数
print permutation( 10 , 2 ), ' \n ' # 5 选 2 排列数
print permutation( 10 ,duplicate = True), ' \n ' # 允许重复的全排列
li = [ ' a ' , ' b ' , ' c ' ]
print ' 全排列： ' ,permutation(li), ' \n '
print ' 选2 ： ' ,permutation(li, 2 ), ' \n '
print ' 允许重复 ： ' ,permutation(li,duplicate = True), ' \n '
raw_input()
![[递推]双幂序列、多幂序列、双幂积序列的和](https://ucc.alicdn.com/pic/developer-ecology/kdeaw43ozhj44_82b9c48dcfe64a14aecc74741eb82b11.png?x-oss-process=image/resize,h_160,m_lfit)
