However, a correct solution would only take one argument, so we’re still not quite there. So a quick fix to that line, adding just, will fix the first issue. This is just unnecessary, since our for loop below will catch the 'cb' case later on. Then the algorithm will, in the base case, add to res before passing it back. The duplicates are being caused by the line res +=. My initial inclination to solve the first problem was to use Python’s built-in set datatype. In other words, it doesn’t solve the problem. For another, it takes two arguments, not one. For one thing, it produces duplicates in our list, which is obviously not what we want. I eventually came up with something like this: def permute1(start, rest):īut it’s embarrassing. I’m writing it up here both to cement my own understanding of the problem and to help people get clear on what really is a fairly basic example of recursion in Python. I was asked this in a somewhat high-pressure situation, and although I could come up with this explanation in English, I couldn’t produce the solution as cleanly as I would have liked. So if we’re on 'b' and we’ve gotten the list, we’d add 'b' to those, resulting in 'bac' and 'bca', each of which we’d add to our final results. Once you have the list from step 2, add each element from that list to the character from the initial string, and append the result to our list of final results. So, for example, if the current iteration is on 'b', we’d want to find all the permutations of the string 'ac'. For each character in the initial string, set aside that character and get a list of all permutations of the string that’s left.Iterate through the initial string – e.g., ‘abc’.Put in English, we want to do the following: Now, immediately this should look like a recursive problem. Write a function permute such that: permute('abc') →
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |