Рекурсивный алгоритм для генерации всех перестановок длины k списка в Python - PullRequest
Новая
       16

Рекурсивный алгоритм для генерации всех перестановок длины k списка в Python

0 голосов
/ 16 сентября 2018

Я хочу создать рекурсивный алгоритм, который будет генерировать все перестановки заданной длины списка целых чисел некоторой длины n.

Вот моя идея:

Для каждого элемента в списке я могу удалить его, затем попросить мою рекурсивную функцию вернуть мне все перестановки длины k-1, а затем к каждой из этих перестановок я добавлю удаленное число. Затем повторите этот процесс для всех номеров в списке.

Базовые случаи: когда список пуст или содержит только один элемент. В этих случаях я просто возвращаю список. То есть до тех пор, пока k меньше или равно длине списка (например, если k равно 3, но l = [1,2], я не могу произвести какие-либо перестановки длины k).

Вот что я написал: 

def permutations(l, k):
w = len(l)
if (k <= w): # list is bigger than the length each permutations
    if (w <= 1):
        return list(l)
    else:
        result = []
        for element in l:
            listSmaller = l[:element] + l[element+1:]
            for perm in permutations(listSmaller, k-1):
                result.append([perm] + element)
        return result      
else: # list is not bigger than the length of the permutations, impossible.
    print("k cannot exceed length of list")

Я продолжаю получать TypeError: can only concatenate list (not "int") to list

Как мне изменить это?

Ответы [ 2 ]

0 голосов
/ 16 сентября 2018

Есть две проблемы:

Первый : [perm] + element Здесь вы добавляете список к целому числу.

Второй : listSmaller = l[:element] + l[element+1:] Здесь вам нужен индекс для доступа к элементам списка. В настоящее время вы используете элементы в качестве индекса и, следовательно, получите IndexError, потому что когда element=4, element+1 будет 5, но у вас нет l[4+1:].

Ваш код работает, когда я делаю следующие изменения в вашем коде. Я только показываю измененные линии. Я не уверен, что результат соответствует ожиданиям. Вы можете попробовать и сообщить мне. 

for i, element in enumerate(l):
    listSmaller = l[:i] + l[i+1:]

    for perm in permutations(listSmaller, k-1):
        result.append([perm] + [element])
0 голосов
/ 16 сентября 2018

В python при использовании 

for a in b:

'a' на самом деле не число, которое можно использовать в качестве индекса, а вместо этого указатель на фактический элемент в списке 'b'.Другими словами, если бы у меня был следующий список 

b = ["Bob", "Jim", "Jane"]

Тогда на первой итерации «а» будет равно «Боб», а не 0.

Когда вы хотите сгенерироватьиндексные номера вместо указателей на элементы можно использовать: 

for a in range(0, len(b)):

вместо.Используя это, ваш код должен работать.

Например, 

for element in range(0, len(l)):
    listSmaller = l[:element] + l[element+1:]
    for perm in permutations(listSmaller, k-1):
        result.append([perm] + element)
return result
...