Рекурсивная функция, которая возвращает комбинации размера n, выбранные из списка - PullRequest
Новая
       39

Рекурсивная функция, которая возвращает комбинации размера n, выбранные из списка

0 голосов
/ 27 апреля 2019

Я пытаюсь написать рекурсивную функцию, которая принимает в качестве входных данных целое число n и список l и возвращает список всех комбинаций размера n, которые можно выбрать из элементов l. Я знаю, что могу просто использовать itertools, но я хочу стать лучше в написании рекурсивных функций, и я верю, что написание собственной функции поможет мне.

Так, например, если вы введете:

n = 3

l = [1, 2, 3, 4]

Я хочу вывод:

`[[1, 2, 3], [1, 3, 4], [2, 3, 4], [1, 2, 4]]

Пока я написал этот код: 

def get_combinations(l, n): # returns the possible combinations of size n from a list of chars

    if len(l) == 0:
        return []

    elif n == 1:
        return [l[0]]

    newList = list()

    for i in range(len(l)):

        sliced_list = l[i:]
        m = n - 1

        #lost here, believe I need to make a recursive call somewhere with get_combinations(sliced_list, m)

    return newList

Я нашел этот пример такой функции для перестановок полезным, но я изо всех сил пытаюсь реализовать нечто подобное.

Чтобы уточнить, я настроил свои базовые случаи так, как я это сделал, потому что я ожидаю передать sliced_list и m в моем рекурсивном вызове, и если вы представите ситуацию, когда i = 3, вы будете у вас есть пустой список для sliced_list, и m будет равен 1, когда вы ушли достаточно глубоко, чтобы создать комбинацию. Но я не женат на этих базовых случаях.

Позвольте мне попытаться обобщить мои вопросы:

  1. Как получить окончательный результат, который представляет собой список списков, а не список списков списков ... (глубина = n)?

  2. Как должен выглядеть мой рекурсивный вызов?

  3. Я иду об этой проблеме совершенно неправильно?

1 Ответ

0 голосов
/ 27 апреля 2019

Сначала я бы порекомендовал вам макет вашей функции следующим образом: 

def get_combinations(array, n):
    solutions = []

    # all the code goes here

    return solutions

Таким образом, если есть проблема, такая как n == 0, вы можете просто проигнорировать ее и получить действительный (пустой)результат.Следующая проблема в том, что эта строка неверна: 

elif n == 1:
    return [array[0]]

Правильно, если n == 1 будет возвращать массив с каждым элементом массива, заключенным в list: 

if n == 1:
    solutions = [[element] for element in array]

Этот является вашим базовым вариантом, так как следующий уровень в рекурсии будет основан на этом.Что будет дальше, так это суть проблемы.Если n > 1 и массив имеет содержимое, то нам нужно перебрать индексы массива.Для каждого мы будем рекурсивно обращаться ко всему, что находится за текущим индексом и n - 1: 

sub_solutions = get_combinations(array[index + 1:], n - 1)

. Это возвращает частичное решение.Нам нужно заполнить элемент на текущим индексом, т.е.array[index], в начале каждого sub_solution в sub_solutions, и добавьте каждый дополненный sub_solution в наш список solutions, который мы возвращаем в конце функции: 

solutions.append([array[index]] + sub_solution)

И это все!

...