Find all permutations of string using recursion

Question

Background: I am somewhat new to programming and only two weeks into learning Python. Currently trying to improve my understanding of recursion, which has been a tough concept for me to implement.

Question: Is this a proper implementation of recursion or just an iterative approach with recursive flare? Or maybe neither? Looking for any tips/suggestions, not necessarily just the "correct" solution.

Code:

import math
def get_permutations(sequence):
 '''
 Enumerate all permutations of a given string
 sequence (string): an arbitrary string to permute. Assume that it is a
 non-empty string. 
 Returns: a list of all permutations of sequence
 '''
 if len(sequence) == 1:
 return list(sequence)
 else:
 char_to_insert = sequence[:1] 
 remainder = sequence[1:] 
 sub_permutations = get_permutations(remainder) 
 permutations = []
 for permutation in sub_permutations: 
 str_len = len(permutation)
 for i in range(0, str_len + 1): 
 front = permutation[:i]
 back = permutation[i:]
 permutations.append(front + char_to_insert + back)
 return permutations

• J_H: Comparing <= 1 would deal with empty input more gracefully. Lose the extra import. A doctest wouldn't hurt. The space complexity of this approach is larger than necessary. As a caller of this routine, I would much rather accept values from a generator than wait for a giant list to be allocated. Sometimes the caller will find the answer early, before needing to explore the entire search space, so the "lazy" aspect of a generator that yields values can be a big win.
• Ξένη Γήινος: I hate to be rude, but your code is very inefficient. There is a function in the standard library that already does this. It is itertools.permutations. It is very efficient and way more Pythonic than your code, and it is what you should use. To get your result, just use: from itertools import permutations def get_permutations(string): return [''.join(mutation) for mutation in permutations(string)].
• Ξένη Γήινος: As for the algorithm, I found better custom implementations here, as it is not mine I cannot claim credit for it and post as an answer.

Answer 1

It's fine to reinvent the wheel. Overheated comments to the contrary, it's perfectly fine to use classic algorithms as a vehicle to practice your coding skills. Just be aware, if you didn't know already, that itertools.permutations does exactly what you need. Using that function as a reference point, your code is producing correct results -- which is great. [The lone exception is your handling of empty inputs, which you explicitly declare out-of-scope. For details on that topic, see this question.] In addition to working correctly, your code is well organized, includes a docstring, uses communicative variable names, and is not too difficult to read and understand. That is a good start on your Python journey.

Consider yielding rather than returning a list. Because permutations scale so rapidly, this is the kind of situation where implementing a generator makes a lot of sense. It allows a caller, for example, to ask for an impossibly large permutation, consume some of its emitted data, and then stop consuming.

Strive for more intuitive implementations. My primary critique, and it's a mild one, is that your algorithm is not nearly as intuitive as others I've seen for permutations. A key skill in programming is recognizing when your implementation is less readable and more complicated that it ought to be. I'm not entirely certain how one acquires this skill; it's one of those "I know it when I see it" phenomena. In any case, the code in the illustration below has several advantages over your implementation: (1) simpler algorithm and less code; (2) comments that wrap an intuitive narrative around the algorithm; (3) a variable naming scheme that helps the reader understand the relevant parts (a collection of xs, the current x, and all of the other_xs); and (4) an implementation that emits the permutations in "lexicographic order according to the order of the input iterable", which is handy for testing and checking (the quote comes from the documentation for itertools.permutations).

def get_permutations(xs):
 if len(xs) == 1:
 yield xs[0]
 else:
 # Every X should get a chance to be the first.
 for i, x in enumerate(xs):
 # Yield X plus each permutation of the other Xs.
 other_xs = xs[0 : i] + xs[i + 1 : None]
 for p in get_permutations(other_xs):
 yield x + p

Next steps. One addition would be to correctly handle empty sequences or raise a ValueError if given one. Along a different track would be to generalize the function to handle any iterable as input. The latter is more challenging because it means we cannot use things like len(xs), xs[0], or xs[0 : i].

• b-mitch: Thank you so much for your thoughtful response! Generators are actually a new concept for me so I am going to explore this further and I will absolutely work on writing more intuitive code. Quick Q: Why use xs[i + 1: None] instead of xs[i + 1]? Thanks again!
• FMc: @b-mitch I use xs[0 : i] + xs[i + 1 : None] rather than xs[: i] + xs[i + 1:] purely for stylistic/readability reasons. I find that explicit sequence slicing just hits my eyeballs more directly, bringing my brain along more quickly as I read code. It's not a stylistic practice I see widely in Python code, so you should go with whatever approach you prefer.
• J_H: Larry Wall asserts there's more than one way to skin a cat, while GvR explains there preferably should be only one obvious way to do it. There's a reason I've not recently authored any functions in perl. The 0 is minor but the None is jarring. In the current code I would find xs[:i] + xs[i + 1:] much more readable, and more likely to be merged down to main after code review. // OTOH an expression like xs[i:foo], where foo might be conditionally assigned None, makes perfect sense, especially if it's an optional kwarg.
• FMc: @J_H Larry Wall was, of course, right. JAPH,
• RootTwo: The last two lines can also be written as yield from (x + p for p in get_permutations(other_xs))