排列穷举算法

今天看到一篇博文 玩个算法题：1-5的排列组合问题 觉得挺有意思。鉴于博主写的是死代码，于是决定自己实现一个动态排列穷举算法，问题抽象为从不重复元素集合 n 中抽取 r 个元素进行排列，总共有多少种不同的排列？

代码如下：

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

from copy import copy

# 排列穷举练习

# 从 集合 n 中选取 r 个元素进行排列，穷举所有排列
# n，待排列元素组成的集合，可以是 list 或者 set 或者 tuple
# r，从 n 中选取 r 个元素，进行排列
# return, list
def permute(n, r):
    if len(set(n)) < len(n): # 有重复元素
        raise error("元素重复")

    n = tuple(n)

    item_count = len(n)

    if item_count < r: # r 不能大于 n 元素的个数
        raise error("r 不能大于 n 中元素的数目")

    flag = [0 for x in xrange(0,r)]

    # 根据 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()