permutation codes don't give the correct result

Question

I wrote a some functions to output the permutation of a list, I gave an input: [1], it's supposed to output [[1]], but my codes output: [[]], I've tried to print logs, looks like in the middle of the code run it did printout [[1]], but not sure why at the end it output [[]]? And how to fix it? Anybody can help? Thanks a lot!

def permute(nums):
    result=[]
    visited=[False]*len(nums) 
    nums=sorted(nums)
    dfs(nums, visited, [], result)
    return result

def dfs(nums, visited, tmp, result):

    if len(tmp)==len(nums):
        result.append(tmp)
        print(result) ##here it shows correctly [[1]]
        return

    for i in range(len(nums)):
        if visited[i]:
            continue

        if i>0 and tmp[i]==tmp[i-1] and not visited[i-1]:
            continue

        tmp.append(nums[i])
        visited[i]=True
        dfs(nums, visited, tmp, result)
        visited[i]=False
        tmp.pop()


a=[1]
result=permute(a)
print("------")
print(result)

you have added `tmp` to `result` and then you pop item from `tmp` which effects your `result` variable to be blank again. — N.Moudgil, Feb 05 '20 at 04:23

Grismar · Answer 1 · 2020-02-05T04:29:37.103

Oh, you're making things very hard on yourself...

Inside of dfs you are calling dfs like this:

dfs(nums, visited, tmp, result)

Then, in that second iteration, you're adding tmp to result like this:

result.append(tmp)

Then, once you return, you remove 1 from tmp with this:

tmp.pop()

That removes it from tmp, but since you added the list tmp to result as well, you've now changed result from [[1]] to [[]] - it's tmp in there after all.

You should reconsider what's needed exactly here. And in Python, passing variables around by reference like you're doing and modifying their contents is not a very good approach. Try thinking about it functionally, without relying on side effects.

If the answer I gave sounds complicated, that's because you've created a fairly complicated solution to what is really a simple problem in Python. For example, here's a simpler solution:

def permutations(xs):
    if len(xs) < 2:
        yield xs
    else:
        for n in range(len(xs)):
            for continuation in permutations(xs[:n] + xs[n+1:]):
                yield [xs[n]] + continuation


print(list(permutations([1,2,3,4])))

Nevermind this:

from itertools import permutations

print(list(permutations([1,2,3,4])))

By the way, you could fix your code like this:

result.append(list(tmp))

This would create a copy instead of adding tmp itself. But once you try your code with a longer list, like [1,2] you'll run into some more errors and I haven't looked at fully debugging the solution.

You're welcome - if you feel the answer is sufficient, please accept it, so others know the question no longer needs an answer and other people looking for the answer can more easily find it. — Grismar, Feb 05 '20 at 23:38

Redowan Delowar · Answer 2 · 2020-02-05T05:21:52.430

If you care about implementation details, check out the answer given by Grismar. Also, look into this answer where the author has explained two approaches of computing permutation of a list of numbers.

However, if you just want the answer with terse code, use the builtin itertools module.

import itertools

def permute(nums):

  # the permutation function returns itertools.permutations object
  result = itertools.permutations(nums)

  # convert the object to your desired format
  result = [list(i) for i in result]

  return result

# call the function
a = [1]
result = permute(a)
print(result)

This should show,

[[1]]

permutation codes don't give the correct result

2 Answers2