CODEWITHSUNDEEP
pythonalgorithmpermutation
Amanda Wang
Amanda Wang

Reputation: 83

permutation codes don't give the correct result

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)

Upvotes: 1

Views: 78

Answers (2)

rednafi
rednafi

Reputation: 1731

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]]

Upvotes: 0

Grismar
Grismar

Reputation: 31319

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.

Upvotes: 1

Related Questions