2
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Oct 18 '17 at 3:31
  • \$\begingroup\$ 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. \$\endgroup\$ – Stack crashed Oct 19 '17 at 14:23
  • \$\begingroup\$ 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. \$\endgroup\$ – Stack crashed Oct 19 '17 at 22:49
  • \$\begingroup\$ @Stackcrashed Thanks I kinda figured that out already... hence my own implementation \$\endgroup\$ – grayQuant Oct 19 '17 at 22:54
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – grayQuant Oct 20 '17 at 0:12
2
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ 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." \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Oct 20 '17 at 16:40
  • 1
    \$\begingroup\$ @SamOnela "In place in an iterative way" is a legitimate justification of superiority. \$\endgroup\$ – 200_success Oct 20 '17 at 17:57
  • \$\begingroup\$ okay - I see your meta post about this type of answer... noted. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Oct 20 '17 at 18:02
  • \$\begingroup\$ 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. \$\endgroup\$ – throws_exceptions_at_you Mar 2 '18 at 14:32
1
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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()))
\$\endgroup\$
  • \$\begingroup\$ grayQuant is probably doing a leetcode problem. For that the class and method signatures are given. \$\endgroup\$ – Stack crashed Oct 19 '17 at 14:18
  • \$\begingroup\$ This is your assumption which cannot be derived from their question. \$\endgroup\$ – Richard Neumann Oct 19 '17 at 14:24
  • \$\begingroup\$ Could the downvoter elaborate on what's wrong with my review? \$\endgroup\$ – Richard Neumann Oct 19 '17 at 14:27
  • \$\begingroup\$ @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. \$\endgroup\$ – grayQuant Oct 19 '17 at 22:10
  • \$\begingroup\$ 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. \$\endgroup\$ – grayQuant Oct 20 '17 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.