Python递归排列
我在尝试使用递归编写置换代码时遇到了麻烦。这将返回一个列表，其中包含每个字母的所有可能位置。因此，对于单词cat，应该返回['cat','act',atc,'cta','tca','tac']。到目前为止，我有这个
def permutations(s):
lst=[]
if len(s) == 1 or len(s) == 0 :
# Return a list containing the string, not the string
return [s]
# Call permutations to get the permutations that don't include the
# first character of s
plst = permutations(s[1:])
print(plst)
for item in plst:
print (item)
plst= permutations(s[1+1:])
# Now move through each possible position of the first character
# and create a new string that puts that character into the strings
# in plst
for i in range(len(s)):
pass
# Create a new string out of item
# and put it into lst
# Modify
for item in lst:
print(index)这里有一些步骤，但我不确定如何使用它们。
回答 10
Stack Overflow用户
发布于 2012-10-28 21:59:00
你想做递归，所以你首先要弄清楚递归是如何工作的。在这种情况下，如下所示：
permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]最后一个条件是：
permutation [a] = [a]因此，递归将列表拆分成子列表，每次提取一个元素。然后，将该元素添加到子列表的每个排列的前面。
所以在伪代码中：
def permutation(s):
if len(s) == 1:
return [s]
perm_list = [] # resulting list
for a in s:
remaining_elements = [x for x in s if x != a]
z = permutation(remaining_elements) # permutations of sublist
for t in z:
perm_list.append([a] + t)
return perm_list这有帮助吗？
Stack Overflow用户
发布于 2016-06-14 05:09:47
递归地，考虑基本情况，并根据直觉进行构建。
1)当只有一个字符'c‘时会发生什么？该元素只有一个排列，所以我们返回一个只包含该元素的列表。
2)我们如何在给定最后一个排列的情况下生成下一个排列？在前面的排列'c‘中的所有可能位置加上一个额外的字母'a’，就得到了'ca'，'ac‘。
3)我们可以通过在每个较早的排列中的所有可能位置添加一个额外的字符来继续构建越来越大的排列。
如果字符串包含一个或更少的字符，下面的代码将返回一个包含一个字符的列表。否则，对于不包括字符串s-1中最后一个字符的所有排列，我们为每个可以包括该字符的位置生成一个新字符串，并将新字符串附加到当前排列列表中。
def permutations(s):
if len(s) <= 1:
return [s]
else:
perms = []
for e in permutations(s[:-1]):
for i in xrange(len(e)+1):
perms.append(e[:i] + s[-1] + e[i:])
return permsStack Overflow用户
发布于 2013-04-08 22:54:19
当你迷失在递归函数中时，你应该画出调用树。下面的版本(灵感@Ben答案)保持输入顺序(如果输入是按字典顺序的，则排列列表将是'012' -> ['012', '021', '102', '120', '201', '210']。
def permut2(mystr):
if len(mystr) <= 1:
return [mystr]
res = []
for elt in mystr:
permutations = permut2(mystr.replace(elt, ""))
for permutation in permutations:
res.append(elt + permutation)
return res以下版本适用于字符串和列表，请注意重构步骤不同：
def permut(array):
if len(array) == 1:
return [array]
res = []
for permutation in permut(array[1:]):
for i in range(len(array)):
res.append(permutation[:i] + array[0:1] + permutation[i:])
return res作为练习，你应该画出这些函数的调用树，你注意到什么了吗？
https://stackoverflow.com/questions/13109274
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号