先來復(fù)習(xí)一下概率論的基礎(chǔ)知識(shí)：
n 個(gè)數(shù)，從中取 m 個(gè)進(jìn)行進(jìn)行排列，有多少中排法。
如果不同位置可以重復(fù)：
第 1 個(gè)位置有 n 種選法
第 2 個(gè)位置有 n 種選法
......
第 m 個(gè)位置有 n 種選法
根據(jù)乘法原理：總共 n**m 種排法
如果不能重復(fù)
第 1 個(gè)位置有 n 種選法
第 2 個(gè)位置有 n-1 種選法
......
第 m 個(gè)位置有 n-m+1 種選法
根據(jù)乘法原理：
總共 n*(n-1)*....*(n-m+1)種排法
全排列就是 n! 種排法 |
|
|
如果我們要編程生成所有的排列，基本上都是嵌套循環(huán)
假如 list 有 n 個(gè)元素，從中選 2 個(gè)進(jìn)行排列，偽代碼基本如下
for i=0 to list.length-1
for j=0 to list.length-1{
//找到一種排列方法
temp=list[i,j]
//根據(jù)情況排除重復(fù)
..
}
問題是上面的例子，我們知道選 2 個(gè)元素排列，所以循環(huán)是 2 層。
但是，如果我們求得是 P(list,n)，n 并不確定，我們不知道循環(huán)是幾層，要想寫一個(gè)通用的函數(shù)，只能借鑒上面的思想，但是不能使用上面的形式
我的想法是：
1、用一個(gè)數(shù)組 repeat[] 來保存每層的循環(huán)變量：repeat[0] 保存第 0 層循環(huán)變量的位置，repeat[1] 保存第 1 層循環(huán)變量的位置......repeat[n-1] 保存第 n-1 層循環(huán)變量的位置
2、標(biāo)記當(dāng)前正在第幾層循環(huán)：layer
3、集合長(zhǎng)度已知 ：size = list.length
4、臨時(shí)數(shù)組：temp[]，長(zhǎng)度為 n
3、算法描述如下：
循環(huán)體（layer == 0 且 repeat[0]== size 則退出循環(huán)）
{
如果（前 n-1 層）
{
取出該層循環(huán)變量：pos=repeat[layer]
如果 (pos 到達(dá)該層末尾，即 pos==size)
{
temp[layer]=null
repeat[layer]=0//該層循環(huán)變量歸零
layer--//回到上一層
continue
}
否則
{
temp[layer]=list[pos]
repeat_count[layer]++//該層循環(huán)變量增加1
layer++//層數(shù)增加 1
continue
}
否則（在最內(nèi)層）
{
不停改變 temp 最后一個(gè)元素，每改變一次，就得到一種新的組合，該層循環(huán)變量增加1
當(dāng)最內(nèi)層也到達(dá) List 末尾：將該層循環(huán)變量歸零，回到上層
}
}
下面是我用 Python 編寫的 permutation 函數(shù)，接受三個(gè)參數(shù)
第一個(gè)參數(shù)：如果數(shù)字則返回排列數(shù)；如果是集合，則返回排列的集合
第二個(gè)參數(shù)：選幾個(gè)數(shù)排列，默認(rèn)全排序
第三個(gè)參數(shù)：是否允許重復(fù)，默認(rèn)不允許
例子：
print permutation(10),'\n' #全排列數(shù)
print permutation(10,2),'\n' #10 選 2 排列數(shù)
print permutation(10,duplicate=True),'\n' #允許重復(fù)的全排列
li=['a','b','c']
print '全排列：',permutation(li),'\n'
print '選2 ：',permutation(li,2),'\n'
print '允許重復(fù) ：',permutation(li,duplicate=True),'\n'
運(yùn)行結(jié)果：
下面給出源代碼：
排列
#!/usr/bin/python
# -*- coding:GBK -*-
def permutation(arr,n=None,duplicate =False):
""" arr : 如果是數(shù)字，則返回全排列數(shù)；如果是數(shù)組，則返回全排列集合
n : 元素個(gè)數(shù)，默認(rèn)全排列
duplicate: 同一個(gè)元素是否可以放在多個(gè)位置，默認(rèn)不允許
注釋:如果允許元素重復(fù)，n 個(gè)位置，每個(gè)位置 size 種選法，排列數(shù) size ** n
"""
#需要排列的數(shù)目，默認(rèn)全排列
if(n==None):
if(type(arr) is int):n=arr
else:n=len(arr)
#元素?cái)?shù)目
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)'
#第一個(gè)元素是數(shù)字，則返回全排列數(shù)目
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
#循環(huán)計(jì)數(shù)器，一層一個(gè)，共 n 個(gè)，都初始化為 0
repeat_count=[0 for i in range(0,n)]
#當(dāng)前正在循環(huán)的層
layer=0
#隨著計(jì)數(shù)器和層數(shù)不停變化的臨時(shí)組合,N 維數(shù)組
v_temp=[None for i in range(0,n)]
result=[]
#當(dāng)前在第 0 層，且第 0 層計(jì)數(shù)器達(dá)到末尾時(shí)退出循環(huán)
while (repeat_count[0]<size) or (layer>0):
if(layer<n-1):
#小于 n-1 層
pos=repeat_count[layer]
if(pos<size):
# 層計(jì)數(shù)器 < size ，保存層計(jì)數(shù)器指向的元素，計(jì)數(shù)器前進(jìn)一位，增加一層
if(not duplicate):
#不允許重復(fù)
if ((pos+1) in repeat_count):
#檢查到重復(fù)，計(jì)數(shù)器前進(jìn)一位，繼續(xù)
repeat_count[layer]=repeat_count[layer]+1
continue
v_temp[layer]=arr[pos]
repeat_count[layer]=repeat_count[layer]+1
layer=layer+1
else:
# 否則，層計(jì)數(shù)器歸零，向上一層
v_temp[layer]=None
repeat_count[layer]=0
layer=layer-1
else:
#第 n-1 層：計(jì)數(shù)器每移動(dòng)一個(gè)位置，都是一種組合
pos=repeat_count[layer]
if(pos<size):
if(not duplicate):
#不允許重復(fù)
if ((pos+1) in repeat_count):
#檢查到重復(fù)，計(jì)數(shù)器前進(jìn)一位，繼續(xù)
repeat_count[layer]=repeat_count[layer]+1
continue
v_temp[layer]=arr[pos]
#找到一種組合，添加至結(jié)果集中
result.append([it for it in v_temp])
#層計(jì)數(shù)器前進(jìn) 1 位
repeat_count[layer]=repeat_count[layer]+1
else:
# n-1 層計(jì)數(shù)器到達(dá)末尾，將層計(jì)數(shù)器歸零 ，返回上層
repeat_count[layer]=0
layer=layer-1
return result
if __name__ == "__main__":
print permutation(10),'\n' #全排列數(shù)
print permutation(10,2),'\n' #5 選 2 排列數(shù)
print permutation(10,duplicate=True),'\n' #允許重復(fù)的全排列
li=['a','b','c']
print '全排列：',permutation(li),'\n'
print '選2 ：',permutation(li,2),'\n'
print '允許重復(fù) ：',permutation(li,duplicate=True),'\n'
raw_input()
//==========================================
posted on 2009-07-29 00:49
左洸 閱讀(1790)
評(píng)論(2) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法