递归函数来开发排列 [英] Recursive function to develop permutations
问题描述
我正试图想出一种方法来开发给定值列表的所有n长度排列。下面的简短功能似乎有效，但我不能确认这是一个更好的方法。不是计算机科学家，我发现
递归函数令人恐惧和不自然。如果有人能告诉我完成这个的pythonic成语，我将不胜感激。
感谢您的帮助，
Steve Goldman
### START CODE ###
def permute（list，n，initialize = True）：
"""递归函数，其返回所有长度n的排序列表
list的排列，长度k。""
如果初始化：
全局排列，permutation_list
permutation = []＃此列表包含各个排列。它
一次构建一个元素
permutation_list = []＃这个列表是包含所有
排列的列表
n = n-1＃这对于排列的每个元素都倒计时。这是一个
本地变量，
#so每个后续函数调用对于列表中的e减少了一个
：
permutation.append（e）
如果n> 0：＃也就是说，排列需要额外的元素
permute（list，n，False）
else：＃换句是长度n
permutation_list.append（permutation [：]）#store完成的
排列
permutation.pop（-1）＃敲掉最后一个值并转到下一个
元素在list中
return permutation_list
if __name __ ==''__ main__''：
list = [''red''，''white''，''blue''，''green'']
print permute（list，3）
你好史蒂夫，
我正在尝试提出一种方法来开发给定值列表的所有n长度排列。
### START CODE ###
...
附注：
请确保在发布到新组时，您的行数少于
78个字符长。
我将问题（如果我理解正确的话）分解为两个问题：
1.查找大小为n的所有子列表l
2.查找列表的所有排列l
使用生成器总是很有趣:-)
：
＃！/ usr / bin / env python
def子列表（l，n）：
'''' ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
如果len（l）== n：＃递归基础
收益率l
返回
for i in range（len（l））：＃删除一个项目并递归
for sub in sublists（l [：i] + l [i + 1：]，n）：
yield sub
def permutations（l）：
'''''''''''''''''''''''''''''''''''''''''''''
如果len（l）== 1：#Rercursion base
yield l
return
for i，v in enraterate （l）：
表示排列（l [：i] + l [i + 1：]）：
收益率[v] + p
def subperm（l，n）：
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' '''
用于子列表中的s（l，n）：
表示排列：
yield p
if __name__ ==" __ main __"：
来自sys import argv
l = range（int（argv [1 ]））
n = int（argv [2]）
对于子精子（l，n）中的p，
：
打印p / /
HTH。
-
----------------- -------------------------------------------------- -----
Miki Tebeka< mi ********* @ gmail.com>
http://tebeka.spymac.net
儿童和成人之间的唯一区别是价格玩具中的
2004年10月19日星期二上午12:34:57 +0000，Steve Goldman写道：
我试图想出一种方法来开发给定值列表的所有n长度排列。下面的简短功能似乎有效，但我不能帮助他们思考这是一种更好的方法。不是计算机科学家，我觉得递归函数是令人恐惧和不自然的。如果有人能告诉我完成这个的pythonic成语，我将不胜感激。
### START CODE ###
[ snip]
Combinatorics（排列，组合等）获得高尔夫（最短/最快）
每年几次clpy。检查groups.google.com以获取一些解决方案。
如果你想要快速，请尝试使用probon包装器在一起使用
py中包装的一些组合数据的probstat.sf.net。披露：我写了。
-Jack
Steve Goldman< st ***** @ ix.netcom。 COM>写道：
我想找到一种方法来开发给定值列表的所有n长度排列。下面的简短功能似乎有效，但我不能帮助他们思考这是一种更好的方法。不是计算机科学家，我觉得递归函数是令人恐惧和不自然的。如果有人能告诉我完成这个的pythonic成语，我将不胜感激。
递归自然定义的东西的实现是
通常最简单的递归（除非有一些手册
相当于尾调用优化，这很容易和自然）。并且
组合数学中的很多东西通常都会自然地受到
递归定义的影响。
如果你希望找到一个自然流畅的非递归实现，
首先考虑一个非递归定义（替代方法是将递归放入
，然后通过显式引入堆栈来删除它;它是
有效，但不一定很漂亮。
在这种情况下，在我看来你很幸运：有一个非递归的
定义X值列表中的长度N的排列。它可能会像... b / b
每个结果都是一个有N个插槽的容器。每个槽，独立地，
假定每个X值，产生X ** N个结果
这就像说（如果X值是数字）在基数X）中，
结果是一个以X为基数从0到X ** N-1的数字。事实上，X
值可能是任意的，但是
列表中的值的INDICES是数字0到X-1，即，确切地说基数为X的数字。
因此，我们将问题简化为计算任意基数，
所以很容易解决非-recursively。例如：
def permute（Xs，N）：
permutations = []
permutation = [None] * N
X = len（Xs）
$ x $ b for x in xrange（X ** N）：
for j in xrange（N）：
i，k = divmod（i，X）
permutation [j] = Xs [k]
permutations.append（list（permutation））
返回排列
这里，我们使用i作为实际计数，整数和内循环
做每个i的''基础扩展''加上索引用相应的X替换每个
数字。
注意我'已经调用了参数Xs，* NOT * list，因为我想使用
内置名称''list''用于正常目的：制作新列表
这是现有的一个副本（我更喜欢这样的愚蠢成语，如
排列[：]，排列+ []或排列* 1，即使它们都是
做同样的工作，最后一个是真正的char我认为
列表（排列）更具可读性。
一般情况下，最好避免构建阴影 - 在上下文中的名称
，你可能想要使用名称的原始含义。
当然，还有其他方法可以计数：
def permute（Xs，N）：
permutations = []
permutation = [0] * N
X = len（Xs）
而True：
$ x $ b为x in xrange（N）：
permutation [ k] + = 1
如果置换[k]< X：休息
排列[k] = 0
其他：
休息
permutations.append（[Xs [k]为排列中的k]）
返回排列
在这里，我需要使用列表理解（或稍微更模糊一些
构造，例如map（Xs .__ getitem __，permutation）...）在追加时间，
来构建索引列表中的X项目列表（数字） ）
算法自然生成。我用
小端方式保持数字，顺便说一句，因为它稍微简单一点，而且你没有为结果指定任何特定的顺序。
这些解决方案中的每一个都可以通过将其变为生成器来增强 -
在开始时删除permutations = []，转换permutations.append
调用yield语句。但是，你必须将简单的
" print permute（...转换为打印列表（peruteute（...）在你的测试用例中。
没什么大不了的，如果你确实需要一个列表;那么你想要的是什么
就是为了对结果进行循环，在这种情况下就是不需要
将它整合到一个占用内存空间的列表中。
这些计数解决方案是否比递归解决方案更简单？
真的不这么认为，一个干净实现的递归（一个没有
全局和第一次切换......！ - ），例如： br />
def permute（Xs，N）：
如果N< = 0：
收益率[]
返回
$ x $ b for x in Xs：
for sub in permute（Xs，N-1）：
yield [x] +在我看来，这个具有强大的简单优势。但是，考虑到计数方法，
仍然具有指导意义。 / >
再次第二次：它所做的所有计数都是+ = 1并检查是否达到某种
限制。但是那非常接近
迭代器的工作，所以为什么不尝试直接使用迭代器而不是那个
基数为X的数字/ 索引成Xs数...？ Python通常更喜欢
直接迭代值而不是数字...
def permute（Xs，N）：
state = [iter（Xs）for k in xrange（N）]
permutation = [s.next（）for s in state]
而True：
收益率列表（置换）
$ x $ b表示x inrange（N）：
try：permutation [k] = state [k] .next（）
除了StopIteration：
state [k] = iter（Xs）
permutation [k] = state [k] .next（）
其他：
休息
其他：
休息
A或许有点可爱，尤其是两个其他：休息。回到
回来（一个用于试图声明突破for，一个用于for
声明突破）。
等等，等等。很有趣的人可以探讨这些问题。
但是，为了简单起见，递归仍然很难被击败; - ）。
Alex
Hi,
I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can''t
help thinking there''s a better way. Not being a computer scientist, I find
recursive functions to be frightening and unnatural. I''d appreciate if
anyone can tell me the pythonic idiom to accomplish this.
Thanks for your help,
Steve Goldman
###START CODE###
def permute(list,n,initialize=True):
"""A recursive function that returns a list of all length n ordered
permutations of "list", length k."""
if initialize:
global permutation, permutation_list
permutation=[] #This list holds the individual permutations. It
is built one element at a time
permutation_list=[] #This list is the list that will contain all
the permutations
n=n-1 #This counts down for each element of the permutation. It is a
local variable,
#so each subsequent function call has n reduced by one
for e in list:
permutation.append(e)
if n>0: #that is,the permutation needs additional elements
permute(list,n,False)
else: # the permutation is length n
permutation_list.append(permutation[:]) #store the completed
permutation
permutation.pop(-1) # knock off the last value and go to the next
element in "list"
return permutation_list
if __name__==''__main__'':
list=[''red'',''white'',''blue'',''green'']
print permute(list,3)
解决方案Hello Steve,
I am trying to come up with a way to develop all n-length permutations of a
given list of values.
###START CODE###
...
Side note:
Please make sure that when posting to a newgroup your lines are less than
78 charcters long.
I''d split the problem (If I understand it correctly) to two problems:
1. Find all sublist of size n of l
2. Find all permutations of a list l
And using generators is always fun :-)
Something in the lines of:
#!/usr/bin/env python
def sublists(l, n):
''''''All sublists in length ''n'' of ''l'' ''''''
assert(len(l) >= n)
if len(l) == n: # Recursion base
yield l
return
for i in range(len(l)): # Remove one item and recurse
for sub in sublists(l[:i] + l[i+1:], n):
yield sub
def permutations(l):
''''''All permuatations of ''l'' ''''''
if len(l) == 1: # Rercursion base
yield l
return
for i, v in enumerate(l):
for p in permutations(l[:i] + l[i+1:]):
yield [v] + p
def subperm(l, n):
''''''All permutation of sublists in size ''n'' of ''l'' ''''''
for s in sublists(l, n):
for p in permutations(s):
yield p
if __name__ == "__main__":
from sys import argv
l = range(int(argv[1]))
n = int(argv[2])
for p in subperm(l, n):
print p
HTH.
--
------------------------------------------------------------------------
Miki Tebeka <mi*********@gmail.com>
http://tebeka.spymac.net
The only difference between children and adults is the price of the toys
On Tue, Oct 19, 2004 at 12:34:57AM +0000, Steve Goldman wrote:Hi,
I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can''t
help thinking there''s a better way. Not being a computer scientist, I find
recursive functions to be frightening and unnatural. I''d appreciate if
anyone can tell me the pythonic idiom to accomplish this.
###START CODE###
[snip]
Combinatorics (permutations, combinations, etc) get golfed (shortest/fastest)
on c.l.py a couple times a year. Check groups.google.com for some solutions.
If you want fast, try probstat.sf.net which does some combinatorics in C with
a python wrapper. disclosure: I wrote it.
-Jack
Steve Goldman <st*****@ix.netcom.com> wrote:
Hi,
I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can''t
help thinking there''s a better way. Not being a computer scientist, I find
recursive functions to be frightening and unnatural. I''d appreciate if
anyone can tell me the pythonic idiom to accomplish this.
The implementation of something that is naturally defined recursively is
often simplest when done recursively (unless there''s some manual
equivalent of a "tail call optimization" that''s easy and natural). And
many things in combinatorics are generally subject to naturally
recursive definitions.
If you hope to find a natural and smooth non-recursive implementation,
think first about a non-recursive definition (the alternative is putting
the recursion in, then removing it by explicitly introducing a stack; it
works, but is not necessarily pretty).
In this case it seems to me that you''re lucky: there IS a non-recursive
definition of "permutations of length N out of a list of X values". It
may go something like...:
each result is a container with N slots. each slot, independently,
assumes each of the X values, yielding X**N results
This is like saying that (if the X values are digits in base X) the
result is a number counting in base X from 0 to X**N-1. In fact, the X
values may be arbitrary, but the INDICES of the values in the list that
holds them ARE the numbers 0 to X-1, i.e., exactly the digits in base X.
So, we have reduced the problem to one of counting in an arbitrary base,
so it becomes pretty easy to solve non-recursively. For example:
def permute(Xs, N):
permutations = []
permutation = [None] * N
X = len(Xs)
for i in xrange(X**N):
for j in xrange(N):
i, k = divmod(i, X)
permutation[j] = Xs[k]
permutations.append(list(permutation))
return permutations
Here, we''re using i as an actual count, an integer, and the inner loop
does the ''base expansion'' of each i, plus the indexing to replace each
digit with the corresponding item of Xs.
Note that I''ve called the argument Xs, *NOT* list, because I want to use
the built-in name ''list'' for its normal purpose: making a new list
that''s a copy of an existing one (I prefer that to such goofy idioms as
permutation[:], permutation+[], or permutation*1, even though they all
do the same job and the last one is a real characters-saver; I think
list(permutation) is more readable, personally).
In general, it''s best to avoid shadowing built-in names in a context
where you''re likely to want to use the original meaning of the names.
Of course, there ARE other ways to count:
def permute(Xs, N):
permutations = []
permutation = [0] * N
X = len(Xs)
while True:
for k in xrange(N):
permutation[k] += 1
if permutation[k] < X: break
permutation[k] = 0
else:
break
permutations.append([Xs[k] for k in permutation])
return permutations
Here, I need to use a list comprehension (or some slightly more obscure
construct, such as map(Xs.__getitem__, permutation)...) at append time,
to construct the list of items of Xs from the list of indexes ("digits")
which the algorithm naturally generates. I hold digits in a
little-endian way, btw, simply because it''s marginally simpler and you
did not specify any particular ordering for the result.
Each of these solutions can be enhanced by making it into a generator --
remove the permutations=[] at the start, turn the permutations.append
call into a yield statement. However, you''ll have to turn the simple
"print permute(..." into a "print list(permute(..." in your testcase.
No big deal, if you do need a list as a result; it''s frequent that what
you want is to LOOP over the result, in which case there''s no need to
make it into a list taking memory space all at once.
Are these "counting" solutions any simpler than the recursive one? I
don''t really think so, for a cleanly-implemented recursion (one without
globals and a first-time switch...!-) such as:
def permute(Xs, N):
if N <= 0:
yield []
return
for x in Xs:
for sub in permute(Xs, N-1):
yield [x]+sub
it seems to me this one has a strong simplicity advantage. However,
considering the "counting" approaches is still instructive. Take the
second one again: all the counting it does is a += 1 and a check if some
limit is reached that way. But that''s VERY close to the job of an
iterator, so why not try to use an iterator directly instead of that
"digit in base X"/"index into Xs" number...? Python generally prefers
iterating directly over values, rather than over digits...
def permute(Xs, N):
state = [iter(Xs) for k in xrange(N)]
permutation = [s.next() for s in state]
while True:
yield list(permutation)
for k in xrange(N):
try: permutation[k] = state[k].next()
except StopIteration:
state[k] = iter(Xs)
permutation[k] = state[k].next()
else:
break
else:
break
A bit cutesy, perhaps, particularly with the two "else: break" back to
back (one for the try statement breaking out of the for, one for the for
statement breaking out of the while).
And so on, and so forth. There''s hardly any limit to the fun one can
have exploring such problems.
But, for simplicity, recursion is still hard to beat;-).
Alex
这篇关于递归函数来开发排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
