我在尝试使用递归制作排列代码时遇到了麻烦。这假设将列表返回到具有每个字母的所有可能位置的使用。因此，对于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)
有步骤，但我不知道如何使用它们
你想做递归，所以你首先要弄清楚递归是如何工作的。在这种情况下，它是以下内容：
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
这有帮助吗？
递归地，考虑基本情况并从这种直觉构建。
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 perms
当你在递归函数中丢失时，你应该绘制调用树。以下版本（灵感来自@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
作为练习，你应该绘制这些函数的调用树，你注意到了什么吗？
def permutations(string_input, array, fixed_value=""):
for ch in string_input:
permutations(string_input.replace(ch, ""), array, fixed_value + ch)
if not string_input:
array.append(fixed_value)
你可以叫它
array = []
permutations("cat", array)
print array
这是我提出的最简单的解决方案。
def permutations(_string):
# stores all generated permutations
permutations = []
# this function will do recursion
def step(done, remain):
# done is the part we consider "permutated"
# remain is the set of characters we will use
# if there is nothing left we can appened generated string
if remain == '':
permutations.append(done)
else:
# we iterate over the remaining part and indexing each character
for i, char in enumerate(remain):
# we dont want to repeat occurance of any character so pick the remaining
# part minus the currect character we use in the loop
rest = remain[:i] + remain[i + 1:]
# use recursion, add the currect character to done part and mark rest as remaining
step(done + char, rest)
step("", _string)
return permutations
你可以测试它：
@pytest.mark.parametrize('_string,perms', (
("a", ["a"]),
("ab", ["ab", "ba"]),
("abc", ["abc", "acb", "cba", "cab", "bac", "bca"]),
("cbd", ["cbd", "cdb", "bcd", "bdc", "dcb", "dbc"])
))
def test_string_permutations(_string, perms):
assert set(permutations(_string)) == set(perms)
您可以使用通过列表迭代索引的函数，并生成一个列表，该列表由索引处的值后跟其余列表值的排列组成。下面是使用Python 3.5+中的功能的示例：
def permutations(s):
if not s:
yield []
yield from ([s[i], *p] for i in range(len(s)) for p in permutations(s[:i] + s[i + 1:]))
所以list(permutations('abc'))回归：
[['a', 'b', 'c'],
['a', 'c', 'b'],
['b', 'a', 'c'],
['b', 'c', 'a'],
['c', 'a', 'b'],
['c', 'b', 'a']]
我知道这也是一个我，但我觉得这个人可能更容易理解......
def permute（s）：
out = []
if len(s) == 1:
out = [s]
else:
for i,let in enumerate(s):
for perm in permute(s[:i]+s[i+1:]):
out += [let+perm]
return out