6
\$\begingroup\$

I've written the following code to print all the permutations of a list. For example:

\$[1, 2, 3]\$ has these permutations: \$[1,2,3]\$, \$[1,3,2]\$, \$[2,1,3]\$, \$[2,3,1]\$, \$[3,1,2]\$, and \$[3,2,1]\$.

def insert_each_position(self, nums, insert_one):
    res, len_of_nums = [], len(nums)
    for idx in range(len_of_nums+1):
        tmp = nums[:]
        tmp.insert(idx, insert_one)
        res.append(tmp)
    return res

def permute(self, nums):
    res, len_of_nums = [[]], len(nums)
    for idx in range(len_of_nums):
        cur_num = nums[idx]
        tmp = []
        for sub in res:
            tmp.extend(self.insert_each_position(sub, cur_num))
        res = tmp
    return res
\$\endgroup\$
5
\$\begingroup\$

As suggested by @netme in the comments, unless you need to write the permutation code yourself, it would be much better to use itertools.permutations, as so:

import itertools

for perm in itertools.permutations([1, 2, 3]):
    print(perm)

That code is more compact, memory-efficient and faster than yours. The itertools module has been deliberately honed to be fast (I think it’s written in C rather than pure Python) and is worth looking into if you haven’t used it before – it’s really useful.


Assuming that you're supposed to be writing your own permutation, here are some comments on that code.

(Given the self parameter and the self.insert_each_position in the second function, I’m assuming these are class methods. I put them in their own class for testing.)

  • Unless tuple unpacking makes the code cleaner or the variables are related, I'm generally inclined to split variable definitions over multiple lines. So I’d split the variable declarations over two lines in the start of each function.

    I would then get rid of the len_of_nums variable. It’s much clearer just to use len(nums) directly in the two places where this variable is used.

  • You don’t mention whether you’re using Python 2 or 3. If you’re using 2, you should use xrange() instead of range(), which is slightly faster and more memory efficient.

  • There are no comments or docstrings. I had to guess how the function worked. You should explain what the code is trying to achieve, and why you wrote it that way – it will make it easer for me to review, and other people to use.

    I would also suggest trying to pick better variable names. res and tmp are not particularly descriptive or useful.

  • My concern with your approach is that you gradually build up a list of all the permutations, which is going to be very memory inefficient and slow. Your program began to struggle when I asked it to permute range(10). It think it has exponential growth, but I’m not sure.

    If you want something fast and you can’t use itertools, I suggest you consider looking at generators for yielding individual permutations. That’s a lot more memory efficient, and will be much faster.

\$\endgroup\$

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.