![]() ![]() # We will put 'b' into our used array as the first character. # We finish the recursive chain, and replace 'a' in left and remove 'a' from used. # All subsequent recursive calls down this path will have 'a' as the first character. # We will put 'a' into our used array as the first character. We have to reset the contents of left and used so that when we continue on in the for loop, we can access the next character properly.įor example, on the first iteration of 'ab': # First iteration: The tricky part comes in after we make the recursive call. ![]() Since our sub_routine will return all of its subsequent permutations, we can concatenate the result of our recursive call with our combos array. What we'll do is pass in the new used and left lists to a recursive call to our sub_routine. For each permutation we start building, we need to add on all combinations of remaining characters. We can then push that permutation to our combos list.Īnd now, here comes the fun part. We're not implementing restrictions on the size of the permutations, so each iteration will represent a unique permutation. The used list will represent our permutation so far. Then, we'll remove the character from the left list at that index and add it to the end of the used list. Looping the index and not the character itself, will make it easier to manage the recursion later on. ![]() First, we'll loop through each index in the left list. Inside our sub_routine function, we can begin generating our permutations. We can call sub_routine in our parent function beginning with an empty list for 'used' characters, and a list made of all characters in the target string as the initial 'left' characters. The first will hold on to all the characters that we have 'used' so far, and the other will hold on to the characters that we still have left to use. We'll pass in two list arguments to sub_routine. We'll also create a combos list to hold onto our permutations. To set it up, we'll have our primary function, string_permutations, but also define a subroutine that will do our recursive dirt work. In my quest to learn the intricacies of Python, I came across one of my favorite algorithms finding all the possible permutations of a string. Menu Finding All Permutations of a String in Python 01 February 2016 on Python, Algorithms ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |