20.06.2023 14:15
shoenfield 12 3200 Источник

Всем доброго времени суток!

Эта коротенькая заметка посвящена симпатичной задачке генерации в лексикографическом порядке всех правильных скобочных последовательностей. Её нередко включают в список задач для подготовки к собеседованию (например, здесь).

По просторам инета гуляет следующее решение:

def  gen_parentheses(parentheses_count, str_, left, right, out_file):
    if left == parentheses_count and right == parentheses_count:
        out_file.write(str_ + "\n")
    return
    if left < parentheses_count:
        gen_parentheses(parentheses_count, str_ + "(", left + 1, right, out_file)
    if right < left:
        gen_parentheses(parentheses_count, str_ + ")", left, right + 1, out_file)

with open("input.txt") as in_file:
    parentheses_count = int(next(in_file))
with open("output.txt", "w") as out_file:
    gen_parentheses(parentheses_count, "", 0, 0, out_file)

Оно, несмотря на его изящную простоту, вызывало чувство некоторой неудовлетворённости :). Присмотревшись, я понял, чем был вызван мой творческий зуд :) –подсознательно не нравилось, что на добавление каждой скобки требовался отдельный вызов функции. Конечно, хотелось бы сократить глубину рекурсии. Сделать это оказалось совсем не сложно.

Ну, во-первых, очевидно, что если число добавленных открывающихся скобок достигло заданного, то нет смысла добавлять соответствующие закрывающиеся скобки по одной – можно сразу добавить все недостающие закрывающиеся скобки:

def  gen_parentheses_v1(parentheses_count, str_, left, right, out_file):
    if left < parentheses_count:
        gen_parentheses_v1(parentheses_count, str_ + "(", left + 1, right, out_file)
        if right < left:
            gen_parentheses_v1(parentheses_count, str_ + ")", left, right + 1, out_file)
    else:
        out_file.write(str_ + (parentheses_count-right)*")" + "\n")

А во-вторых, да и с открывающимися скобками можно не тормозить :) – добавлять не по одной, а сразу строкой из нескольких открывающихся скобок и одной закрывающейся: 

def gen_parentheses_v2(parentheses_count, str_, left, right, out_file):
    if left < parentheses_count:
        for i in range(parentheses_count, max(left, right+1) - 1, -1):  
            gen_parentheses_v2(parentheses_count,
                               str_ + (i-left)*"(" + ")",
                               i,
                               right + 1,
                               out_file)
    else:
        out_file.write(str_ + (parentheses_count-right)*")" + "\n")

В итоге глубина рекурсии снизилась более чем в два раза :)

Комментарии (12)


  1. dyadyaSerezha
    20.06.2023 16:25
    #25671512

    И ни одного типа у параметров или возврата функции...


  1. ialexander
    20.06.2023 16:25
    #25671574
    +6

    А вы тестировать пробовали? Вот результат работы gen_parentheses_v1 для parentheses_count = 3:

    (()))

    ()())

    ()))

    )))

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

    К слову говоря, бага и в gen_parentheses сразу видна, там return в самом начале функции. Подозреваю и в gen_parentheses_v1 проблемы с отступами. Ну да, похоже у else некорректный отступ.


    1. shoenfield Автор
      20.06.2023 16:25
      #25672932

      Доброе утро! Огромное спасибо! Когда набивал заметку на Хабре, накосячил с отступами :) Поправил


  1. Zara6502
    20.06.2023 16:25
    #25671588
    +1

    В статье нет самой задачи, поэтому непосвящённым непонятна суть телодвижений.


    1. miga
      20.06.2023 16:25
      #25671956
      +1

      Это типичная задача на кодинг интервью, у нее нет цели, только путь


      1. Zara6502
        20.06.2023 16:25
        #25672718

        ТЗ есть всегда, я не посещаю кодинг-интервью, ответ ниже уже дали.


    1. Alexandroppolus
      20.06.2023 16:25
      #25672336
      +2

      Судя по коду, генерация всех правильных скобочных последовательностей длины 2*n


    1. domix32
      20.06.2023 16:25
      #25673894
      +2

      Дано число n. Необходимо сгенерировать строки длинной 2*n с валидными перестановками открывающих и закрывающих скобок.

      n = 3
// валидные
()()()
()(())
(())()
((()))
// не валидные
)(())(
))))))
((()()
...

      Закономерно решается через рекурсивные функции.


  1. Alexandroppolus
    20.06.2023 16:25
    #25672572
    +6

    В итоге глубина рекурсии снизилась более чем в два раза

    Если уж тут начали бороться с рекурсией, то в оной борьбе надо идти до конца! )) Вот исходный вариант, переделанный на цикл самым простым и тупым способом:

    Код
    function genParentheses(n) {
    const arr = [];
    const stack = [-1];
    let left = 0, right = 0;
    let action = 0;

    while (action >= 0) {
        switch(action) {
            case 0: 
                if (left === n && right === n) {
                    console.log(arr.join(''));
                    action = stack.pop();
                } else {
                    action = 1;
                }
                break;
            case 1:
                if (left < n) {
                    arr.push('(');
                    left++;
                    stack.push(2);
                    action = 0;
                } else {
                    action = 3;
                }
                break;
            case 2:
                left--;
                arr.pop();
                action = 3;
                break;
            case 3:
                if (right < left) {
                    arr.push(')');
                    right++;
                    stack.push(4);
                    action = 0;
                } else {
                    action = stack.pop();;
                }
                break;
            case 4:
                right--;
                arr.pop();
                action = stack.pop();;
                break;
        }
    }
}

genParentheses(3);

    Можно скопипастить в консоль браузера и там вызвать


    1. mrCOTOHA
      20.06.2023 16:25
      #25673872

      Если это перевести на ЯП топикстартера - получится не очень хорошо. Свитч (точнее match) пока тормозной в питоне. Я из-за него не смог, однажды, в Яндексовской задачке по времени уложиться :( Лучше на if ... elif заменить.


  1. volatilization
    20.06.2023 16:25
    #25678274

    Если честно, не понял вывода об уменьшении глубины рекурсии. Разве глубина не зависит от входящего параметра чуть ли не линейно? Ну и вроде бы параметры линейно меняются в последующих вызовах.


    1. Alexandroppolus
      20.06.2023 16:25
      #25678710

      В исходном варианте рекурсия глубиной 2N, поскольку каждый рекурсивный вызов увеличивает на 1 либо left, либо right, пока оба не вырастут с 0 до N. А в итоговом решении на каждом уровне рекурсии right на 1 больше, а left не менее чем right-1, итого на глубине N+1 достигается граница рекурсии left == N.

      N - это parentheses_count, количество открывающих скобок.