blocks|key|1628620|text|你想做递归，所以你首先要弄清楚递归是如何工作的。在这种情况下，如下所示：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1628621|permutation+[a,b,c,...]+=+[a+%2B+permutation[b,c,...],+b+%2B+permutation[a,c,..],+...]|code-block|syntax|javascript|1628622|最后一个条件是：|1628623|permutation+[a]+=+[a]|1628624|因此，递归将列表拆分成子列表，每次提取一个元素。然后，将该元素添加到子列表的每个排列的前面。|1628625|所以在伪代码中：|1628626|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]+%2B+t)

+++return+perm_list|1628627|这有帮助吗？|1628628|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|Z|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|10|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|11|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

You want to do recursion, so you first have to find out how the recursion would work. In this case it is the following:

<pre><code>permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]
</code></pre>

And as a final condition:

<pre><code>permutation [a] = [a]
</code></pre>

So the recursion splits up the list in sublists with one element extracted each time. Then this element is added to the front of each of the permutations of the sublist.

So in pseudo-code:

<pre><code>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
</code></pre>

Does this help?

blocks|key|1628639|text|当你迷失在递归函数中时，你应该画出调用树。下面的版本(灵感@Ben答案)保持输入顺序(如果输入是按字典顺序的，则排列列表将是'012'+->+['012',+'021',+'102',+'120',+'201',+'210']。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1628640|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+%2B+permutation)
++++return+res|code-block|syntax|javascript|1628641|以下版本适用于字符串和列表，请注意重构步骤不同：|1628642|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]+%2B+array[0:1]+%2B+permutation[i:])
++++return+res|1628643|作为练习，你应该画出这些函数的调用树，你注意到什么了吗？|1628644|entityMap^0|1Q|1F|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|W|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|X|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|Y|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|D|@]|E|$]]]|R|$]]

When you're lost in recursive function, you should draw the call tree. The following version (inspired @Ben answer) keep the input order (if the input is in lexicographic order, the list of permutations will be, <code>'012' -&gt; ['012', '021', '102', '120', '201', '210']</code>.

<pre><code>def permut2(mystr):
 if len(mystr) &lt;= 1:
 return [mystr]
 res = []
 for elt in mystr:
 permutations = permut2(mystr.replace(elt, ""))
 for permutation in permutations:
 res.append(elt + permutation)
 return res
</code></pre>

The following version works for strings and lists, notice the reconstruction step is not the same:

<pre><code>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
</code></pre>

As an exercice, you should draw call tree of the these functions, do you notice something ?

blocks|key|5551382|text|递归地，考虑基本情况，并根据直觉进行构建。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5551383|1)当只有一个字符'c‘时会发生什么？该元素只有一个排列，所以我们返回一个只包含该元素的列表。|5551384|2)我们如何在给定最后一个排列的情况下生成下一个排列？在前面的排列'c‘中的所有可能位置加上一个额外的字母'a’，就得到了'ca'，'ac‘。|5551385|3)我们可以通过在每个较早的排列中的所有可能位置添加一个额外的字符来继续构建越来越大的排列。|5551386|如果字符串包含一个或更少的字符，下面的代码将返回一个包含一个字符的列表。否则，对于不包括字符串s-1中最后一个字符的所有排列，我们为每个可以包括该字符的位置生成一个新字符串，并将新字符串附加到当前排列列表中。|5551387|def+permutations(s):
++++if+len(s)+<=+1:
++++++++return+[s]
++++else:
++++++++perms+=+[]
++++++++for+e+in+permutations(s[:-1]):
++++++++++++for+i+in+xrange(len(e)%2B1):
++++++++++++++++perms.append(e[:i]+%2B+s[-1]+%2B+e[i:])
++++++++return+perms|code-block|syntax|javascript|5551388|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|U|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|V|8|@]|9|@]|A|$M|N]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Recursively, think about the base case and build from that intuition. 

1) What happens when there's only one character 'c'? There's only one permutation of that element, and so we return a list containing only that element. 

2) How can we generate the next permutation given the last one? Adding an additional letter 'a' at all possible positions in the previous permutation 'c' gives us 'ca', 'ac'.

3) We can continue building larger and larger permutations by adding an additional character at all possible positions in each earlier permutation.

The following code returns a list of one character if the string has one character or less. Otherwise, for all permutations not including the last character in the string s[-1], we generate a new string for each position where we could include that character and append the new string to our current list of permutations. 

<pre><code>def permutations(s):
 if len(s) &lt;= 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
</code></pre>

blocks|key|1632073|text|def+permutations(string_input,+array,+fixed_value=""):
++++for+ch+in+string_input:
++++++++permutations(string_input.replace(ch,+""),+array,+fixed_value+%2B+ch)
++++if+not+string_input:
++++++++array.append(fixed_value)|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1632074|你可以这样调用它|unstyled|1632075|array+=+[]
permutations("cat",+array)
print+array|1632076|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|L|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$B|C]]|$1|I|3|-4|5|F|7|N|8|@]|9|@]|A|$]]]|J|$]]

<pre><code>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)
</code></pre>

You can call it by

<pre><code>array = []
permutations("cat", array)
print array
</code></pre>

blocks|key|5551490|text|我知道这也是一个我，但我认为这对一些人来说可能更容易理解……|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5551491|for循环迭代string.|5551492|Another+循环中的每个字母，递归地置换所有其他可能性，这是|unordered-list-item|5551493|的基本情况。|ordered-list-item|5551494|5551495|5551496|def+permute(s)：out+=+[]+if+len(s)+==+1:+out+=s+else:+for+i，let+in+enumerate:+for+perm+in+permute(s:i%2Bsi%2B1:)：out+%2B=+let%2Bperm+return+out|5551497|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|R|8|@]|9|@]|A|$]]|$1|G|3|H|5|I|7|S|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|T|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

I know this is a me too, but I think this one might be easier for some folks to understand....

<ol>
<li>The base case is when the input is just one character.</li>
<li>Setup up a for loop that iterates through each of the letters in the string.</li>
<li>Another for loop recursively permutes through all the other possibilities. 

<pre><code>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
</code></pre></li>
</ol>

blocks|key|5551533|text|这是我想出的最简单的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5551534|+++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]+%2B+remain[i+%2B+1:]
++++++++++++++++++++#+use+recursion,+add+the+currect+character+to+done+part+and+mark+rest+as+remaining
++++++++++++++++++++step(done+%2B+char,+rest)
++++++++step("",+_string)
++++++++return+permutations|code-block|syntax|javascript|5551535|您可以使用以下命令进行测试：|5551536|@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)|5551537|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

This is the easiest solution I came up with.

<pre><code> 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
</code></pre>

You can test it with:

<pre><code>@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)
</code></pre>

blocks|key|4134061|text|您可以使用一个函数在列表中迭代索引，并生成一个由索引处的值和其余列表值的排列组成的列表。下面是一个使用Python+3.5%2B特性的示例：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4134062|def+permutations(s):
++++if+not+s:
++++++++yield+[]
++++yield+from+([s[i],+*p]+for+i+in+range(len(s))+for+p+in+permutations(s[:i]+%2B+s[i+%2B+1:]))|code-block|syntax|javascript|4134063|因此list(permutations('abc'))返回：|offset|length|style|CODE|4134064|[['a',+'b',+'c'],
+['a',+'c',+'b'],
+['b',+'a',+'c'],
+['b',+'c',+'a'],
+['c',+'a',+'b'],
+['c',+'b',+'a']]|4134065|entityMap^0|0|0|2|P|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@$I|T|J|U|K|L]]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

You can use a function that iterates an index through the list, and yield a list consisting of the value at the index followed by the permutations of the rest of the list values. Below is an example using features from Python 3.5+:

<pre><code>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:]))
</code></pre>

so that <code>list(permutations('abc'))</code> returns:

<pre><code>[['a', 'b', 'c'],
 ['a', 'c', 'b'],
 ['b', 'a', 'c'],
 ['b', 'c', 'a'],
 ['c', 'a', 'b'],
 ['c', 'b', 'a']]
</code></pre>

blocks|key|5551577|text|这些示例代码确实很有帮助，但我在CodeSignal上做代码练习时发现一个测试用例失败了。基本上，这里的所有给定方法都忽略了是否有任何重复的情况。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5551578|Input:+s:+"ABA"+
Output:+["ABA",+"AAB",+"BAA",+"BAA",+"AAB",+"ABA"]+
Expected+Output:+["AAB",+"ABA",+"BAA"]|code-block|syntax|javascript|5551579|因此，如果您看到，它在输出中有以下重复项：|5551580|["BAA",+"AAB",+"ABA"]|5551581|我在这里一点一点地修改了一下。|5551582|def+stringPermutations(s):
++++++++news+=+s
++++++++if+len(news)+==+1:
++++++++++++return+[news]
++++++++res+=+[]
++++++++for+permutation+in+stringPermutations(news[1:]):
++++++++++++for+i+in+range(len(news)):
++++++++++++++++res.append(permutation[:i]+%2B+news[0:1]+%2B+permutation[i:])
++++++++#+To+Remove+Duplicates+From+a+Python+List:+list(dict.fromkeys(res))
++++++++#+To+Sort+List+:+sorted()
++++++++return+sorted(list(dict.fromkeys(res)))

def+main():
++++arr+=+'ABA'
++++print(stringPermutations(arr))

if+__name__+==+'__main__':
++++main()|5551583|但是从时间复杂度来看，这个答案是不合适的。这种方法的时间复杂度为:+o(n%5E2)|5551584|我认为下面的方法是相当合理的。|5551585|def+stringPermutations(string,+prefix,+permutation_list):
++++#Edge+case+check
++++if+len(string)+==+0:
++++++++permutation_list.append(prefix)
++++else:
++++++++for+i+in+range(len(string)):
++++++++++++rem+=+string[0:i]+%2B+string[i+%2B+1:]
++++++++++++stringPermutations(rem,+prefix+%2B+string[i],+permutation_list)
++++return+sorted(list(dict.fromkeys(permutation_list)))
def+main():
++++permutation_list+=+[]
++++print(stringPermutations('aba','',+permutation_list))

if+__name__+==+'__main__':
++++main()|5551586|entityMap|0|LINK|mutability|MUTABLE|url|https://app.codesignal.com/^0|G|A|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@$A|15|B|16|1|17]]|C|$]]|$1|D|3|E|5|F|7|18|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|19|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|1A|8|@]|9|@]|C|$G|H]]|$1|M|3|N|5|6|7|1B|8|@]|9|@]|C|$]]|$1|O|3|P|5|F|7|1C|8|@]|9|@]|C|$G|H]]|$1|Q|3|R|5|6|7|1D|8|@]|9|@]|C|$]]|$1|S|3|T|5|6|7|1E|8|@]|9|@]|C|$]]|$1|U|3|V|5|F|7|1F|8|@]|9|@]|C|$G|H]]|$1|W|3|-4|5|6|7|1G|8|@]|9|@]|C|$]]]|X|$Y|$5|Z|10|11|C|$12|13]]]]

These examples codes are really helpful but I found a test case failed when I was doing a code practice on <a href="https://app.codesignal.com/" rel="nofollow noreferrer">CodeSignal</a>. basically all the given approach here ignoring if there are any duplicates.

<pre><code>Input: s: "ABA" 
Output: ["ABA", "AAB", "BAA", "BAA", "AAB", "ABA"] 
Expected Output: ["AAB", "ABA", "BAA"]
</code></pre>

So, if you see, it has following duplicates in the output:

<pre><code>["BAA", "AAB", "ABA"]
</code></pre>

I modified this by bit here

<pre><code>def stringPermutations(s):
 news = s
 if len(news) == 1:
 return [news]
 res = []
 for permutation in stringPermutations(news[1:]):
 for i in range(len(news)):
 res.append(permutation[:i] + news[0:1] + permutation[i:])
 # To Remove Duplicates From a Python List: list(dict.fromkeys(res))
 # To Sort List : sorted()
 return sorted(list(dict.fromkeys(res)))

def main():
 arr = 'ABA'
 print(stringPermutations(arr))

if __name__ == '__main__':
 main()
</code></pre>

But this answer is not appropriate as per time complexity. Time complexity with this approach is: o(n^2)

I think the below approach is quite reasonable.

<pre><code>def stringPermutations(string, prefix, permutation_list):
 #Edge case check
 if len(string) == 0:
 permutation_list.append(prefix)
 else:
 for i in range(len(string)):
 rem = string[0:i] + string[i + 1:]
 stringPermutations(rem, prefix + string[i], permutation_list)
 return sorted(list(dict.fromkeys(permutation_list)))
def main():
 permutation_list = []
 print(stringPermutations('aba','', permutation_list))

if __name__ == '__main__':
 main()
</code></pre>

blocks|key|1628765|text|def+permute(s):
++++ch+=+list(s)
++++if+len(ch)+==+2:
++++++++per+=+ch[1]+%2B+ch[0]+
++++++++return+[''.join(ch)]+%2B+[per]
++++if+len(ch)+<+2:
++++++++return+ch
++++else:
++++++++return+[+init%2Bper+for+init+in+ch+for+per+in+permute(''.join(ch).replace(init,""))]+|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1628766|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>def permute(s):
 ch = list(s)
 if len(ch) == 2:
 per = ch[1] + ch[0] 
 return [''.join(ch)] + [per]
 if len(ch) &lt; 2:
 return ch
 else:
 return [ init+per for init in ch for per in permute(''.join(ch).replace(init,&quot;&quot;))] 
</code></pre>

blocks|key|1628810|text|通过递归进行排列的最简单方法是首先设想问题的递归树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1628811|​|1628812|📷|atomic|offset|length|1628813|1628814|基本情况:如果给我们一个空的列表排列是[+[]+]，那么我们只想从列表中删除一项，并将其添加到列表的其余所有索引中。|1628815|例如输入:+a，b，c+first+=a+|1628816|+=+b，c+all+=+a，b，c，b，a，c，b，c，a|blockquote|1628817|1628818|时间:+O(+N！)+#这是最好的，因为我们正在创建N！元素|1628819|per_with_all中的空格O(N%5E2)+#N堆栈帧*N项|1628820|1628821|来源：https://www.youtube.com/watch?v=us0cYQXQpxg|1628822|def+permetutation(arr):
++++if+len(arr)+==+0:
++++++++return+[+[]+]
++++#We+remove+1st+item+from+error+as+at+each+level+we+introduce+1+item+
++++first_elenment+=+arr.pop(0)

++++#getting+permet+for+all+other+item+
++++perm_without_first+=+permetutation(arr)

++++per_with_all+=+[]

++++#Add+permtution+to+every+index+
++++for+comb+in+perm_without_first:
++++++++for+ind+in+range(len(comb)%2B1):+#We+also+wan+to+add+elenment+to+last+so+do+%2B1+
++++++++++++all+=+comb[0:ind]+%2B+[first_elenment]+%2B+comb[ind:]+
++++++++++++per_with_all.append(+all)

++++return+per_with_all|code-block|syntax|javascript|1628823|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/37f982ba49f7dbc90cde69fdc818d76e.png|imageAlt|1|LINK|MUTABLE|url|https://www.youtube.com/watch?v=us0cYQXQpxg^0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|3|17|1|0|0^^$0|@$1|2|3|4|5|6|7|1H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1I|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1J|8|@]|9|@$G|1K|H|1L|1|1M]]|A|$]]|$1|I|3|C|5|6|7|1N|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1O|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1P|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|1Q|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|1R|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1S|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1T|8|@]|9|@]|A|$]]|$1|V|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1V|8|@]|9|@$G|1W|H|1X|1|1Y]]|A|$]]|$1|Y|3|Z|5|10|7|1Z|8|@]|9|@]|A|$11|12]]|$1|13|3|-4|5|6|7|20|8|@]|9|@]|A|$]]]|14|$15|$5|16|17|18|A|$19|1A|1B|-4]]|1C|$5|1D|17|1E|A|$1F|1G]]]]

The easiest way to do permutations through recursion
is to first imagine a recursion tree for the problem
<a href="https://i.stack.imgur.com/sqdTL.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/sqdTL.png" alt="enter image description here" /></a>
base case: if we are given an empty list permutation would be [ [] ]
Then we just want to remove an item from the list and add it to all indices of the rest of the list.
<blockquote>
<pre><code>eg input : [a,b,c]
first = a
rest = [b,c]
all = [a,b,c] , [b,a,c] , [b,c,a]
</code></pre>
Time: O(N!) #This is best since we are creating N! element 
Space O(N^2) #N stack frame * N item in per_with_all
</blockquote>
Source:
<a href="https://www.youtube.com/watch?v=us0cYQXQpxg" rel="nofollow noreferrer">https://www.youtube.com/watch?v=us0cYQXQpxg</a>
<pre><code>def permetutation(arr):
 if len(arr) == 0:
 return [ [] ]
 #We remove 1st item from error as at each level we introduce 1 item 
 first_elenment = arr.pop(0)

 #getting permet for all other item 
 perm_without_first = permetutation(arr)

 per_with_all = []

 #Add permtution to every index 
 for comb in perm_without_first:
 for ind in range(len(comb)+1): #We also wan to add elenment to last so do +1 
 all = comb[0:ind] + [first_elenment] + comb[ind:] 
 per_with_all.append( all)

 return per_with_all
</code></pre>

Im having trouble trying to make a permutation code with recursion. This is suppose to return a list back to the use with all the posible position for each letter. so for the word <code>cat</code> it is suppose to return <code>['cat','act',atc,'cta','tca','tac']</code> . so far i have this 

<pre><code>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)
</code></pre>

There are steps there but im not sure how to use them

Python recursion permutations

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我在尝试使用递归编写置换代码时遇到了麻烦。这将返回一个列表，其中包含每个字母的所有可能位置。因此，对于单词cat，应该返回['cat','act',atc,'cta','tca','tac']。到目前为止，我有这个def permutations(s):    lst=[]    if len(s) == 1 or l...

问Python递归排列
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Python递归排列EN