Напечатайте все пути от пункта отправления до пункта назначения на борту, используя рекурсию - Python - PullRequest
Новая
       47

Напечатайте все пути от пункта отправления до пункта назначения на борту, используя рекурсию - Python

0 голосов
/ 05 декабря 2018

У меня есть некоторая проблема для рекурсивного решения без использования какого-либо модуля, и мне нужно, чтобы вы помогли мне, пожалуйста.

Вы находитесь на сетке в начале координат (0, 0), и вы хотитечтобы добраться до пункта назначения n, k (то есть n движется вправо, а k движется вверх).Мы можем двигаться только на один шаг вправо или вверх за раз.Реализуйте функцию, которая получает два числа n, k и печатает все пути, чтобы добраться до места назначения n, k, только шагая вправо или вверх.Шаг вверх представлен как «u», а справа - как «r».Каждый путь должен быть последовательностью символов u, r, и каждый путь должен быть напечатан в одной строке.

Я пытался что-то сделать: 

def paths_ur(n, k):
    paths_ur_helper(n, k, 0, 0)

def paths_ur_helper(n, k, right_moves, up_moves):
    if right_moves == n and up_moves == k: #If we reach the destination there is nothing to return
        return []
    if right_moves < n and up_moves < k: #Check that we are in range of the board
        return 'r' + paths_ur_helper(n, k, right_moves + 1, up_moves) + 
        \ +'u' + paths_ur_helper(n, k, right_moves, up_moves + 1)

Ноэто идет не так, возможно, потому что я не представляю, как работает рекурсия ...

Спасибо.

1 Ответ

0 голосов
/ 05 декабря 2018

Простейшая логика, которую я могу придумать:

  1. Определить координаты x, y пункта назначения.Начальные координаты: (0,0)
  2. Создайте строку с 'u' & 'r', каждая из которых имеет вертикальные и горизонтальные расстояния.
  3. Используйте itertools.permutations, чтобы найти все возможные перестановкиприведенной выше строки и добавьте в ранее пустой список.
  4. Напечатайте каждый уникальный элемент списка.

Код реализации: 

from itertools import permutations
from more_itertools import unique_everseen

x = (0,0)  # start point tuple
y = (1,2)  # End point tuple // You can also get this dynamically via user input, if needed
h = y[0] - x[0]  # horizontal distance (difference of x-coordinates of DST, SRC
v = y[1] - x[1]  # vertical distance (difference of y-coordinates of DST, SRC
plist = [] # blank list to store permutation result
path = 'u'*h + 'r'*v  # gives result as 'uur' (two up and one right, in this case)
for  subset in (permutations(path, h+v)): # use permutations on the path string
    plist.append(subset)                  # append each result to the plist
# print (plist)                           // Optional to verify the code
for item in list(unique_everseen(plist)):
    print ("{}\n".format(item))           # Print unique values from plist in a new line

По какой-то причинемодуль permutations возвращает дубликаты.Отсюда использование «unique_everseen».Надеюсь, это то, что вы хотели.

...