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\$
8
  • 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\$ Commented Oct 18, 2017 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\$ Commented Oct 19, 2017 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\$ Commented Oct 19, 2017 at 22:49
  • \$\begingroup\$ @Stackcrashed Thanks I kinda figured that out already... hence my own implementation \$\endgroup\$ Commented Oct 19, 2017 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\$ Commented Oct 20, 2017 at 0:12

2 Answers 2

Reset to default
1
\$\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
  • 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\$ Commented Oct 20, 2017 at 16:40
  • 1
    \$\begingroup\$ @SamOnela "In place in an iterative way" is a legitimate justification of superiority. \$\endgroup\$ Commented Oct 20, 2017 at 17:57
  • \$\begingroup\$ okay - I see your meta post about this type of answer... noted. \$\endgroup\$ Commented Oct 20, 2017 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\$ Commented Mar 2, 2018 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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.