今天看到一篇博文 玩?zhèn)€算法題：1-5的排列組合問題 覺得挺有意思。鑒于博主寫的是死代碼，于是決定自己實(shí)現(xiàn)一個(gè)動(dòng)態(tài)排列窮舉算法，問題抽象為從不重復(fù)元素集合 n 中抽取 r 個(gè)元素進(jìn)行排列，總共有多少種不同的排列？

代碼如下：

#!/usr/bin/python
# -*- coding:utf-8 -*-

from copy import copy

# 排列窮舉練習(xí)

# 從 集合 n 中選取 r 個(gè)元素進(jìn)行排列，窮舉所有排列
# n，待排列元素組成的集合，可以是 list 或者 set 或者 tuple
# r，從 n 中選取 r 個(gè)元素，進(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 元素的個(gè)數(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 自增算法
    # 自增到最大值時(shí) 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()