V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
lxy42
V2EX  ›  Python

Python itertools 模块中的全排列算法,看起来简单却非常让人费解!

  •  1
     
  •   lxy42 · 2018-02-27 17:41:53 +08:00 · 3257 次点击
    这是一个创建于 2221 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在刷 leetcode 时遇到了全排列问题,想来想去也只能想出递归的解法。然后突然想起 Python 的 itertools 模块中有全排列的函数,模块源码是用 C 写的,不过在官方文档中有提供 Python 版本的代码,代码看起来非常简单,但是我看了很久都看不懂算法的原理是什么。

    接着在 SO 上发现了相关问题,根据“ Alex Martelli ”的回答,该算法涉及到了Cyclic permutation 理论。有兴趣的同学可以研究一下代码和 Cyclic permutation 理论。

    附上代码

    def permutations(iterable, r=None):
        # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
        # permutations(range(3)) --> 012 021 102 120 201 210
        pool = tuple(iterable)
        n = len(pool)
        r = n if r is None else r
        if r > n:
            return
        indices = list(range(n))
        cycles = list(range(n, n-r, -1))
        yield tuple(pool[i] for i in indices[:r])
        while n:
            for i in reversed(range(r)):
                cycles[i] -= 1
                if cycles[i] == 0:
                    indices[i:] = indices[i+1:] + indices[i:i+1]
                    cycles[i] = n - i
                else:
                    j = cycles[i]
                    indices[i], indices[-j] = indices[-j], indices[i]
                    yield tuple(pool[i] for i in indices[:r])
                    break
            else:
                return
    
    11 条回复    2018-02-28 11:50:37 +08:00
    bomb77
        1
    bomb77  
       2018-02-27 17:59:26 +08:00
    谢谢分享,学习了
    jameslan
        2
    jameslan  
       2018-02-27 19:29:30 +08:00 via Android
    C++也有啊
    glasslion
        3
    glasslion  
       2018-02-27 19:50:42 +08:00
    stl 也一样, 全排列的标准算法
    lxy42
        4
    lxy42  
    OP
       2018-02-27 20:34:36 +08:00 via Android
    @jameslan @glasslion 好像网上讨论这个算法的人比较少,我看了大都是递归和字典序算法
    Philippa
        5
    Philippa  
       2018-02-27 21:08:24 +08:00 via Android
    做缓存时蛮方便的
    gnaggnoyil
        6
    gnaggnoyil  
       2018-02-27 21:45:48 +08:00
    NOIP2004 普及组最后一题.我以为已经是常识了……
    locktionc
        7
    locktionc  
       2018-02-27 21:56:08 +08:00 via iPhone
    我一般用的是二进制来做的。
    A->1000
    B->0100
    C->0010
    D->0001

    例如
    0110 对应了 BC
    1011 对应了 A CD

    所以只要计算 1 ( 0001 )到 15 ( 1111 )就可以得到所有组合
    genesislive
        8
    genesislive  
       2018-02-27 23:28:48 +08:00
    @locktionc 4 个字母的全排列不是有 24 种情况吗?计算 1-15 怎么得到所有组合?
    locktionc
        9
    locktionc  
       2018-02-27 23:33:20 +08:00
    @genesislive 我说的是一个类似的题的做法,全排列因此稍稍改一下。
    wizardoz
        10
    wizardoz  
       2018-02-28 11:48:34 +08:00
    @genesislive 他算出的是组合,题主问的是排列
    wizardoz
        11
    wizardoz  
       2018-02-28 11:50:37 +08:00
    @locktionc 受教了! 9 年前大学毕业面试题就做过这题,我一直以为我的解法是对的,今天看到你的答案比我的好多了!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5314 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 07:14 · PVG 15:14 · LAX 00:14 · JFK 03:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.