推荐学习书目
› 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
Python itertools 模块中的全排列算法，看起来简单却非常让人费解!
lxy42 · 2018-02-27 17:41:53 +08:00 · 3365 次点击这是一个创建于 2467 天前的主题，其中的信息可能已经有所发展或是发生改变。
在刷 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
 |
1
bomb77 2018-02-27 17:59:26 +08:00
谢谢分享，学习了
|
 |
2
jameslan 2018-02-27 19:29:30 +08:00 via Android
C++也有啊
|
 |
3
glasslion 2018-02-27 19:50:42 +08:00
stl 也一样， 全排列的标准算法
|
 |
4
lxy42 OP |
 |
5
Philippa 2018-02-27 21:08:24 +08:00 via Android
做缓存时蛮方便的
|
 |
6
gnaggnoyil 2018-02-27 21:45:48 +08:00
NOIP2004 普及组最后一题.我以为已经是常识了……
|
 |
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 ）就可以得到所有组合 |
 |
8
genesislive 2018-02-27 23:28:48 +08:00
@locktionc 4 个字母的全排列不是有 24 种情况吗？计算 1-15 怎么得到所有组合？
|
|
9
locktionc 2018-02-27 23:33:20 +08:00
@genesislive 我说的是一个类似的题的做法，全排列因此稍稍改一下。
|
 |
10
wizardoz 2018-02-28 11:48:34 +08:00
@genesislive 他算出的是组合，题主问的是排列
|
Select Language