коды перестановок не дают правильный результат

Question

Я написал несколько функций для вывода перестановки списка, я дал ввод: [1], он должен выводить [[1]], но мои коды выводят: [[]], я пытался печатать логи, похоже, что в середине выполнения кода он печатал [[1]], но не уверен, почему в конце он выводит [[]]? И как это исправить? Кто-нибудь может помочь? Большое спасибо!

---

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)

Answer 1

О, вы делаете вещи очень тяжело для себя ...

Внутри dfs вы звоните dfs вот так:

dfs(nums, visited, tmp, result)

Тогда, в этом вторая итерация, вы добавляете tmp к result следующим образом:

result.append(tmp)

Затем, как только вы вернетесь, вы удаляете 1 из tmp с этим:

tmp.pop()

Это удаляет его из tmp, но поскольку вы добавили список tmp в result, теперь вы изменили result с [[1]] на [[]] - там tmp в конце концов.

Вы должны пересмотреть то, что нужно именно здесь. И в Python передача переменных по ссылке, как вы делаете, и изменение их содержимого - не очень хороший подход. Попробуйте подумать об этом функционально, не полагаясь на побочные эффекты.

Если ответ, который я дал, звучит сложно, то это потому, что вы создали довольно сложное решение для действительно простой проблемы в Python. Например, вот более простое решение:

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

Не берите в голову это:

from itertools import permutations

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

Кстати, вы можете исправить свой код следующим образом:

result.append(list(tmp))

Это создаст копию вместо добавления tmp. Но как только вы попробуете свой код с более длинным списком, таким как [1,2], вы столкнетесь с еще несколькими ошибками, и я не стал полностью отлаживать решение.

Answer 2

Если вам важны детали реализации, ознакомьтесь с ответом Grismar . Кроме того, посмотрите на этот ответ, где автор объяснил два подхода к вычислению перестановки списка чисел.

Однако, если вы просто хотите получить ответ с кратким кодом, используйте встроенный itertools модуль.

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)

Это должно показать,

[[1]]