О генерации скобочных последовательностей

[dyadyaSerezha]

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

[ialexander]

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

(()))

()())

()))

)))

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

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

[shoenfield]

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

[Zara6502]

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

[miga]

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

[Zara6502]

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

[Alexandroppolus]

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

[domix32]

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

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

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

[Alexandroppolus]

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

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

Код

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);

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

[mrCOTOHA]

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

[krammnic]

Свитч != матч. А матч в питоне нужен для других целей

[wataru]

Еще есть принципиально другое итеративное решение. Похоже на алгоритм Найораны для генерации перестановок в лексикографическом порядке.

Сгенерируем первую последовательность "((....()...))".

Теперь найдем самую правую позицию, где стоит "(", и ее можно поменять на ")". Делаем это и генерируем конец строки в минимальную лексикографически последовательность (жадно ставим все оставшиеся "(", а потом все оставшиеся ")".

Работает за ту же сложность O(n*Сat(n)), что и рекурсивный метод. Код можно посмотреть тут.

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

[volatilization]

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

[Alexandroppolus]

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

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