推荐学习书目
› 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
这是一个创建于 3009 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求如下： 输入一段 list 长度为 M ，和需要随机提取的 list 长度为 N ，返回所有可能的 list 例如输入[1,2,3,4,5,6,7] 3 那么第一个需要返回的自然是[1,2,3] 我在 CSDN 上看到有人写了这样一段递归（原来是 print 我改成 return 了）
special=[]
def ngetmprint(list,ans,m):
if m==len(list):
ans = ans + list
# print(ans)
special.append(ans)
elif m==0:
# print(ans)
special.append(ans)
else:
ngetmprint(list[1:],ans+list[0:1],m-1)
ngetmprint(list[1:],ans,m)
return special
当我想弄清楚他的原理时候，发现在生成完比如[1,2,]后 list 会慢慢自增加到 [ 4,5,6,7 ] 然后再递归那个[1,,3] 对了他那个函数的 ans 填一个空的 list 比如[]就好 有好心人可以帮我讲讲这是怎么回事喵~ PS:至于网上那些尾递归或者罗汉塔循环乘数什么的就不用提了，如果有好的当然不吝赐教~
11 条回复 • 2016-09-08 17:14:51 +08:00
 |
1
crayygy 2016-09-06 17:48:55 +08:00
最直接的方法是自己打几个断点跟下去
|
 |
2
billlee 2016-09-06 22:25:41 +08:00
把自己当成 python 执行一遍
|
 |
3
thekoc 2016-09-07 09:06:13 +08:00
|
 |
4
guyskk 2016-09-07 11:39:40 +08:00 via Android
首先，这个函数的作用是取 ans 中所有的元素+list 中取 m 个元素，然后把 list 中取 m 个元素这个步骤分解为:
这 m 个元素中包含 list 的第一个元素和不包含 list 的第一个元素，把大问题分解为两个小问题递归求解。 |
 |
5
aec4d 2016-09-07 23:30:42 +08:00
@crayygy 的说法是非常误导人的，对于递归算法打断点跟踪栈调用是相当不明智的，因为几行的递归代码会造成非常非常多的函数调用，从数学逻辑上理解递归才是明智的。
上面写的是一个组合算法， python 有自带模块 from itertools import combinations,题主给的代码大意是等同于①取出第一个元素然后算 m-1 的组合，结果加上第一个元素 ②取出第一个元素，算 m 的组合 这个过程在满足递归结束条件的时候把结果加入到 special 列表，属于有去无回，这个过程的 2 步是可以调换位置的，所以代码中调换也不会影响结果 再用另外一种思虑 取出 m 个元素等同于,移除某一个元素，然后算 m 的组合(每个元素都移出一次,排除重复项) https://gist.github.com/anonymous/517607265f6c60cd4d0a94d76018460f 附 2 个觉得写得比较好的递归博文 http://zisong.me/post/suan-fa/ren-nao-li-jie-di-gui http://www.nowamagic.net/librarys/veda/detail/2314 |
 |
6
stillwater 2016-09-08 00:07:19 +08:00
从 list 中取 m 个元素的所有组合 = 除 list 第一个元素外取 m-1 个元素的所有组合 + 除 list 第一个元素外取 m 个元素的所有组合
|
 |
7
popstk 2016-09-08 11:17:43 +08:00  1
组合问题，根据组合公式 C(m,n)=C(m-1,n-1)+C(m, n-1)
ngetmprint(list,ans,m): #C(m,n) len(list)=n ， ans 是保存上次递归已有的元素，第一次调用当然是空的 ngetmprint(list[1:],ans+list[0:1],m-1) #C(m-1,n-1) 这里取 n 的第 1 个即 list[0:1]，仍需从剩下的 list[1:]取 m-1 个 ngetmprint(list[1:],ans,m) #C(m, n-1) 从剩下的 list[1:]取 m 个 要是罗汉塔真的理解了，有了公式相信不难写出 另外跟一下 ans 每次保存的状态，也能帮助理解公式的意义 |
 |
10
ecloud 2016-09-08 16:57:34 +08:00
python 怎么说呢，我的经验是慎用递归
我曾经有过这么一段代码 def getMobilePair(smobile): tmobile = getMobile("") if tmobile == smobile: getMobilePair(smobile) else: return tmobile 其中的 getMobile("")是从一个池中随机取出一个手机号，然后这个递归得到另外一个不相同的随机的手机号 具体的情形我已经有点淡忘了，大概情况是当程序以多线程运行每秒上千次请求（这个递归相关的大约占 5%）的时候， python 递归执行的速度跟不上整体逻辑，出现了一些意想不到的结果 后来我只能把一个号码池分割成两部分，烦别取随机，就再没有出过毛病 |
Select Language