Реализация задачи подъема по лестнице в Python - PullRequest
Новая
       10

Реализация задачи подъема по лестнице в Python

1 голос
/ 17 апреля 2020

Я получил эту проблему на CoderByte. Требовалось найти несколько способов. Я нашел решения для этого в StackOverflow и других сайтах. Но, двигаясь вперед, Мне также нужны все возможные способы, чтобы достичь N-го шага.

Описание проблемы: Существует лестница из N ступеней, и вы можете подняться на 1 или 2 ступеньки за время. Вам нужно посчитать и вернуть общее количество уникальных способов подняться по лестнице. Порядок принятых шагов имеет значение.

Например,

Ввод: N = 3

Ввод: 3

Объяснение: Существует 3 уникальных способа подъем по лестнице из 3 шагов: {1,1,1}, {2,1} и {1,2}

Примечание: может быть другой случай, когда человек может сделать 2 или 3 или 4 шага за один раз (я знаю, что это реально невозможно, но я пытаюсь добавить масштабируемость к шагам ввода в коде)

Я не могу найти правильную логику c, чтобы получить все возможные способы. Полезно, если я получу решение в Python, но это не строгое требование.

Ответы [ 2 ]

2 голосов
/ 17 апреля 2020

Вот минимальное решение с использованием библиотеки itertools: 

from itertools import permutations, chain

solve = lambda n: [(1,)*n] + list(set(chain(*[permutations((2,)*i + (1,)*(n-2*i)) for i in range(1, n//2+1)])))

Для вашего примера введите: 

> solve(3)
[(1, 1, 1), (1, 2), (2, 1)]

Как это работает?

Проще увидеть, что происходит, если мы сделаем шаг назад: 

def solve(n):
    combinations = [(1,)*n]
    for i in range(1, n//2+1):
        combinations.extend(permutations((2,)*i + (1,)*(n-2*i)))
    return list(set(combinations))

Самый тривиальный случай - это случай, когда вы делаете один шаг за раз, поэтому n шаги: (1,)*n. Затем мы можем посмотреть, сколько двойных шагов мы можем сделать максимум, и это пол n , деленный на 2: n//2. Затем мы повторяем возможные двойные шаги: попробуйте добавить двойной шаг к каждой итерации (2,)*i, заполняя оставшееся пространство отдельными шагами (1,)*(n-2*i).

Функция перестановок из itertools сгенерирует все возможные перестановки одиночных и двойных шагов для этой итерации. При вводе (1,1,2) он будет генерировать (1,1,2), (1,2,1) и (2,1,1). В конце мы используем способ преобразования результата в set, чтобы удалить дубликаты, а затем преобразовать его обратно в список.

Обобщение для любого количества и длины шагов (не оптимально!)

Один вкладыш: 

from itertools import permutations, chain, combinations_with_replacement

solve = lambda n, steps: list(set(chain(*[permutations(sequence) for sequence in chain(*[combinations_with_replacement(steps, r) for r in range(n//min(steps)+1)]) if sum(sequence) == n])))

Пример вывода: 

> solve(8, [2,3])
[(3, 2, 3), (2, 3, 3), (2, 2, 2, 2), (3, 3, 2)]

Версия для чтения легче: 

def solve(n, steps):
    result = []
    for sequence_length in range(n//min(steps)+1):
        sequences = combinations_with_replacement(steps, sequence_length)
        for sequence in sequences:
            if sum(sequence) == n:
                result.extend(permutations(sequence))
    return list(set(result))
1 голос
/ 17 апреля 2020 
def solve(n) :
    if (n == 0):
        return [[]]
    else:
        left_results = []
        right_results = []

        if (n > 0):
            left_results = solve(n - 1)
            for res in left_results: # Add the current step to every result
                res.append(1)

        if (n > 1):
            right_results = solve(n - 2)
            for res in right_results: # Same above
                res.append(2)

        return left_results + right_results

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

...