今天看到一篇博文 玩?zhèn)€算法題：1-5的排列組合問題 覺得挺有意思濒募。鑒于博主寫的是死代碼，于是決定自己實現(xiàn)一個動態(tài)排列窮舉算法粤蝎，問題抽象為從不重復(fù)元素集合 n 中抽取 r 個元素進(jìn)行排列外邓，總共有多少種不同的排列侈玄？
代碼如下：
#!/usr/bin/python
# -*- coding:utf-8 -*-
from copy import copy
# 排列窮舉練習(xí)
# 從 集合 n 中選取 r 個元素進(jìn)行排列，窮舉所有排列
# n帜平，待排列元素組成的集合幽告，可以是 list 或者 set 或者 tuple
# r梅鹦，從 n 中選取 r 個元素，進(jìn)行排列
# return, list
def permute(n, r):
if len(set(n)) < len(n): # 有重復(fù)元素
raise error("元素重復(fù)")
n = tuple(n)
item_count = len(n)
if item_count < r: # r 不能大于 n 元素的個數(shù)
raise error("r 不能大于 n 中元素的數(shù)目")
flag = [0 for x in xrange(0,r)]
# 根據(jù) flag 從 n 中取元素
def permute_with_flag(flag):
source = list(n)
target = []
for x in flag:
target.append(source[x])
source.remove(source[x])
return target # 輸出
# flag 自增算法
# 自增到最大值時 return False
def increse_flag(flag):
flag[0] += 1
for x in xrange(0,len(flag)):
if flag[x] == item_count - x:
flag[x] = 0
if x+1 < len(flag):
flag[x+1] += 1
if flag.count(0) == len(flag):
return False
return True
permutation = [permute_with_flag(flag)]
while increse_flag(flag):
permutation.append(permute_with_flag(flag))
return permutation
def main():
n = set((1, 2, 3, 4, 5))
m = permute(n, 5)
for x in m:
print x
if __name__ == '__main__':
main()
