排列穷举算法

作者: 公爵海恩庭斯 | 来源:发表于2015-12-01 15:23 被阅读480次

    今天看到一篇博文 玩个算法题: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()
    

    相关文章

      网友评论

      本文标题:排列穷举算法

      本文链接:https://www.haomeiwen.com/subject/tbvjhttx.html