WedX - журнал о программировании и компьютерных науках

Как сохранить результаты в рекурсивной функции и будет ли вообще работать мой метод?

Моя первая попытка написать рекурсивную функцию, которая выводит список всех перестановок строковых символов.

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

Я знаю, что то, что у меня есть на данный момент, также неверно, поскольку цикл for будет прерван оператором return. Но именно здесь я застрял, как сохранить результаты, то есть каждую отдельную перестановку, без сброса списка до пустого при каждом вызове? Мне не разрешено использовать глобальные переменные, это упражнение из открытого курса MIT.

Также хотел бы знать, будет ли вообще работать мой метод? не уверен, что то, как я нарезал струну, сработает.

Может ли кто-нибудь пролить свет на то, как я могу составить список всех перестановок внутри функции? и если мой метод вообще имеет шанс работать?

def get_permutations(sequence):

if len(sequence) == 1:
    return sequence


else:
    return (sequence[i] + get_permutations(sequence[0:i-1] + sequence[i +
1 : len(sequence)]) for i in range(len(sequence)))

Теперь выход

<generator object get_permutations.<locals>.<genexpr> at 0x102b3b9d0>
python function recursion
17.09.2020

  • Есть много вопросов SO - и других мест - которые подробно описывают, как накапливать результаты при обходе дерева рекурсии. Как правило, вам нужно создать список частичных результатов и вернуть его в качестве значения вашей функции. Что касается того, будет ли это работать? Stack Overflow не является службой тестирования — что происходит, когда вы ее запускаете? Это ваша работа. 18.09.2020
  • Как я уже сказал, я имею в виду метод, а не точный код. Интересно, имеет ли метод реальную ценность. 18.09.2020
  • Это проблема проверки дизайна/кода, а не для переполнения стека. 18.09.2020
  • где бы я спросил? 18.09.2020
  • Я не знаю. Прежде всего, это зависит от того, где именно вы не уверены. Ваш подход, безусловно, действителен, так как вы взяли его из проверенного алгоритма. Я думаю, что ваша реализация - это то, что вы действительно ставите под сомнение, и это требует тестирования. Чтобы узнать, где размещать сообщения, вам следует перейти на главные страницы Stack Exchange и просмотреть существующие группы. Обзор кода касается только улучшения рабочего кода. 18.09.2020
  • Я ниоткуда не брал. Я только что получил это как проблему, и мне показалось, что это можно сделать с помощью рекурсии. Есть ли другой сайт, где люди могут помочь новичкам? Я думал, что этот сайт для этого 18.09.2020
  • Ах, ха! Хорошо... вы заново изобрели полезный подход. 18.09.2020
  • Тогда я вижу ваше замешательство. Пожалуйста, повторите по теме и как спросить из вступительного тура. 18.09.2020

Ответы:


1

Вы не можете return больше одного раза! Вместо того, чтобы возвращать каждое значение из цикла, вы хотите создать список и вернуть его. Это будет выглядеть примерно так:

def get_permutations(sequence):
    if len(sequence) == 1:
        # base case
        return sequence
    
    # Each recursive call needs to be on a subset of sequence so it gets
    # smaller each time and eventually reaches the base case...
    return [
        sequence[i] + get_permutations(sequence[0:i-1] + sequence[i+1:len(sequence)]) 
        for i in range(len(sequence))
    ]

Здесь все еще есть некоторые ошибки в том, как вы сокращаете свой базовый случай и как вы строите список, но, надеюсь, это укажет вам правильное направление!

17.09.2020
  • Да, я изначально пытался со списком, но мне не разрешено использовать глобальные переменные, поэтому мне пришлось инициализировать его пустым, но с каждым вызовом функции (рекурсивно (?)) этот список очищался. Не могли бы вы рассказать, как я могу использовать список, не будучи глобальным? также для базового случая, если длина 1, то есть только перестановка идентичности? так что еще, как не вернуть себя. . . 18.09.2020
  • Я не понимаю дополнительный вопрос - в приведенном выше коде не используются никакие global, и для этого нет никаких причин. Ничто в приведенном выше коде не очищает список. В базовом случае действительно есть проблема - вместо того, чтобы возвращать сам список, он должен возвращать список, содержащий список (т.е. [sequence], а не sequence), поскольку возвращаемое значение должно быть списком списков! 18.09.2020
  • Да, он не использует список, поскольку я изначально пытался использовать список, но каждый раз, когда я запускал код, я получал просто пустой список, поскольку он был установлен пустым при каждом вызове функции, единственный способ, которым я мог видеть, это использовать глобальный список но это запрещено в этом упражнении. Я отредактировал код, как вы предложили, поэтому есть только один оператор возврата, я получаю вывод, с которым я никогда не сталкивался, ‹generator object get_permutations.‹locals›.‹genexpr› по адресу 0x102b3b9d0› Я понимаю, что вы имеете в виду, говоря о его возвращении строка вместо списка строк 18.09.2020
  • Если вы получаете объект генератора, это означает, что вы использовали () вместо [] в этом последнем операторе возврата. 18.09.2020

    • 2

    Поскольку предполагается, что функция возвращает список перестановок, вы должны использовать вложенное предложение for в понимании списка для итерации по возвращаемому списку из рекурсивного вызова для добавления к текущему значению в индексе i. Кроме того, в базовом случае функция также должна возвращать список строковых символов, даже если это список из одного символа:

    def get_permutations(sequence):
    if len(sequence) == 1:
        return [sequence]
    return [
        sequence[i] + s
        for i in range(len(sequence))
        for s in get_permutations(sequence[:i] + sequence[i + 1:])
    ]

    чтобы:

    get_permutations('abc')

    возвращает:

    ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
    17.09.2020
  • Спасибо. Я не знаком с методом перечисления или с использованием двух переменных, как у вас, могу я спросить, буквы i и v или цифры? как вы думаете, мой код можно изменить с помощью основных команд, или мне нужно полностью переписать? Я не могу утверждать, что знаю или правильно понимаю ваше решение, поскольку оно использует методы, которые я еще не рассмотрел. . 18.09.2020
  • Я понимаю. Я обновил свой ответ, чтобы перебрать range(len(sequence)), как вы тогда. 18.09.2020
    • Новые материалы
    Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что это выглядит сложно…
    Просто начните и учитесь самостоятельно Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что он кажется мне сложным, и я бросил его. Это в основном инструмент..
    Лицензии с открытым исходным кодом: руководство для разработчиков и создателей
    В динамичном мире разработки программного обеспечения открытый исходный код стал мощной парадигмой, способствующей сотрудничеству, инновациям и прогрессу, движимому сообществом. В основе..
    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Для любых предложений по сайту: [email protected]