Generate all permutations of a list in Python

Question

This is my solution to the "Permutations" problem from Leetcode:

Given a collection of distinct numbers, return all possible permutations.

I know this is a common routine that can be done much faster using itertools.permutations but I want to write it to learn the algorithm itself.

I would like any general feedback on the implementation of the recursive algorithm. But I am also curious whether I should use an instance helper method as it is now, or make the helper method a class or static method. If someone can show me how to re-write the helper method as a class or static method that would be appreciated.

class Solution(object):
 def permute(self, nums):
 res = []
 self._permuteHelper( nums, 0, res)
 return res
 def _permuteHelper(self, nums, start, results): #helper method
 if start >= len(nums):
 results.append(nums[:])
 else:
 for i in range(start, len(nums)):
 nums[i], nums[start] = nums[start], nums[i]
 self._permuteHelper(nums, start +1, results)
 nums[start], nums[i] = nums[i], nums[start]
s = Solution()
nums = [1, 2, 3]
print s.permute(nums)

There are a lot of suggestions in the comments and answers about using library functions. For programming challenge, I am not interested in copying and pasting library functions. Yes, this is re-inventing the wheel if you want to call it that!

• Oscar Smith: Just for the record, if you ever wanted to actually do this, itertools has the function built in, and faster than anything you will ever come up with.
• Stack crashed: If there are many duplicates your algorithm will be very inefficient. Think about a case where you have 100 of the same integer. In actuality there is only one unique permutations, yet your code will run millions of times even if you use a dictionary to check for uniqueness which you also didn’t even do.
• Stack crashed: If you are really doing this for interview preparation, using built in function to generate permutation for this problem (which focuses on the algorithm of precisely that) wouldn't help you much.
• grayQuant: @Stackcrashed Thanks I kinda figured that out already... hence my own implementation
• grayQuant: @RichardNeumann which tag would you suggest? Usually algorithm tag and programming challenge means writing the routine itself and not simply plugging in a library function. Please check out the other posts that are tagged programming challenge for perspective.

Answer 1

Instead of calling a recursive function you could do it in place in an iterative way.

Like this:

l = [1, 2, 3, 4, 5]
def permute(l):
 n = len(l)
 result = []
 c = n * [0]
 result.append(l)
 i = 0;
 while i < n:
 if c[i] < i:
 if i % 2 == 0:
 tmp = l[0]
 l[0] = l[i]
 l[i] = tmp
 else:
 tmp = l[c[i]]
 l[c[i]] = l[i]
 l[i] = tmp
 result.append(l)
 c[i] += 1
 i = 0
 else:
 c[i] = 0
 i += 1
 return result
print(permute(l))

This is not my algorithm, it is called the Heap algorithm

• Sᴀᴍ Onᴇᴌᴀ: Please read How do I write a good answer?: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted."
• 200_success: @SamOnela "In place in an iterative way" is a legitimate justification of superiority.
• Sᴀᴍ Onᴇᴌᴀ: okay - I see your meta post about this type of answer... noted.
• throws_exceptions_at_you: Thanks @200_success for pointing this out. Yes I implicitly indicate why my script is a superior solution. I might have linked to more reading material.

Answer 2

The algorithm as you have intended looks ok to me.

However I have a few comments about the algorithm's efficiency. With the current approach you will regenerate the same permutation many times if there are repeated integers. Is that what you'd want? I don't think so but if you do discard the rest of this review.

For repeated numbers, to avoid repeated entries in the permutation result set, one approach would be use a dictionary and check if the solution was already added to it. But this gets very inefficient when you have many repeated integers. Think about a list with 10000 instance of the same integer. Like [42, 42, 42,...., 42]. The number of unique permutations possible is exactly 1, yet your algorithm (even with dictionary) will loop many many times just to produce that one result.

To address this, what is typically done is, a dictionary is created that stores the frequency of each integer that is available at a given point. We can do a DFS starting with all available integers and their original count. At each level, when we use up an integer we decrement its frequency by 1 before going further down. And we only can use an integer if the available count is greater than zero. This will generate each unique combination exactly once, so the case mentioned above with 1000 42's would finish quite fast.

Answer 3

Naming a class Solution because it is part of the solution of a coding excercise seems like a very bad practice to me since it does not convey its purpose or the problem it's trying to solve.

In fact, using a class for your problem, may be overkill.
It has no own __init__ implementation and only one exposed method.

Both methods of Solution namely permute and _permuteHelper could be functions, since they do not use any other properties from their class.

Furthermore, as already said in the comments, itertools.permutations already implements your problem's solution.

Also _permuteHelper should be named _permute_helper to comply with PEP8.

If you really require an object-oriented solution, I'd suggest inheriting list and giving it a permutations method:

from itertools import permutations
class PermutableList(list):
 """A list with a permutations method."""
 def permutations(self, len=None):
 """Yields permutations of the list."""
 return permutations(self, len)
if __name__ == '__main__':
 pl = PermutableList(range(1, 4))
 print(list(pl.permutations()))

• Stack crashed: grayQuant is probably doing a leetcode problem. For that the class and method signatures are given.
• Richard Neumann: This is your assumption which cannot be derived from their question.
• Richard Neumann: Could the downvoter elaborate on what's wrong with my review?
• grayQuant: @Stackcrashed yes this is leetcode I'll add that info to my post. But I agree naming it something else can be better for readability.
• grayQuant: Sorry I already know about itertools. I would like a review on the code I have written, not a re-write of how to solve the task.