Рекуррентный подход: Как мы можем генерировать все возможности на фигурных скобках?
Как мы можем генерировать все возможности на фигурных скобках?
Значение N дало нам, и мы должны генерировать все возможности.
Примеры:
1) если N == 1, то только одна возможность ().
2) если N==2, то возможны (()), () ()
3) если N==3, то возможны ((())), (()) (), () () (), () (())...
Примечание: левая и правая скобки должны совпадать. Я имею в виду) (недействительно для N == 1
Можем ли мы решить эту проблему с помощью рекуррентного подхода?
5 ответов
Из википедии -
Дейкское слово - это строка, состоящая из n X и n Y, такая, что ни один начальный сегмент строки не имеет больше Y, чем X (см. Также язык Dyck). Например, ниже приведены слова Дейка длиной 6:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
Повторно интерпретируя символ X как открытые скобки и Y как закрывающие скобки, Cn подсчитывает количество выражений, содержащих n пар скобок, которые соответствуют друг другу:
((())) ()(()) ()()() (())() (()())
Смотрите также http://www.acta.sapientia.ro/acta-info/C1-1/info1-9.pdf
Аннотация. Представлен новый алгоритм генерации всех слов Дейка, который используется для ранжирования и отмены выбора слов Дика. Мы подчеркиваем важность использования слов Дика в кодировании объектов, связанных с каталонскими числами. Как следствие формул, используемых в алгоритме ранжирования, мы можем получить рекурсивную формулу для n-го каталонского числа.
Для данного N мы всегда должны начинать с открытой фигурной скобки. Теперь рассмотрим, где находится соответствующая закрывающая скобка. Это может быть в середине, как в ()() или в конце, как (()) за N=2,
Теперь рассмотрим N=3:
Это может быть в конце: (()()) а также ((())),
Или посередине: ()(()) а также ()()() где он находится в положении 2. Тогда он также может быть в положении 4: (())(),
Теперь мы можем по существу объединить 2 случая, реализовав случай, когда закрывающая скобка находится в конце, такая же, как и в середине, но со всеми возможностями для N=0, добавленными в конец.
Теперь для ее решения вы можете отработать все возможности для n между начальной и конечной скобкой, и аналогично вы можете отработать все возможности для m после окончания скобки. (Заметка m+n+1 = N) Затем вы можете просто объединить все возможные комбинации, добавить их в свой список возможностей и перейти к следующему возможному месту для конечной скобки.
Просто предупреждаю, что с этими типами проблем можно легко ошибиться - найти все возможности для i и для N-i и просто объединить их, но это для N=3 будет в два раза ()()() или, по крайней мере, напечатайте его дважды.
Вот код Python 2.x, который решает проблему:
memoise = {}
memoise[0] = [""]
memoise[1] = ["()"]
def solve(N, doprint=True):
if N in memoise:
return memoise[N]
memoise[N] = []
for i in xrange(1,N+1):
between = solve(i-1, False)
after = solve(N-i, False)
for b in between:
for a in after:
memoise[N].append("("+b+")"+a)
if doprint:
for res in memoise[N]:
print res
return memoise[N]
Вот некоторый код, который по сути является компактной версией кода JPvdMerwe, за исключением того, что он возвращает список решений, а не печатает их. Этот код работает как на Python 2, так и на Python 3.
from itertools import product
def solve(num, cache={0: ['']}):
if num not in cache:
cache[num] = ['(%s)%s' % t for i in range(1, num + 1)
for t in product(solve(i - 1), solve(num - i))]
return cache[num]
# Test
for num in range(1, 5):
print(num)
for s in solve(num):
print(s)
выход
1
()
2
()()
(())
3
()()()
()(())
(())()
(()())
((()))
4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
((()))()
(()()())
(()(()))
((())())
((()()))
(((())))
Вот еще пара функций, выведенных из псевдокода, приведенного в статье, связанной Эдом Гинессом: Генерация и ранжирование слов Дика. В этой статье используется индексация на основе 1, но я преобразовал их для соответствия индексации на основе 0 в Python.
Эти функции медленнее, чем solve функции выше, но они все еще могут быть полезны. pos_dyck_words имеет то преимущество, что оно чисто итеративное. unrank является итеративным, но вызывает рекурсивную вспомогательную функцию f; Ото, f использует кеширование, поэтому оно не такое медленное, как могло бы быть, а только кеширование целых чисел, которое использует меньше оперативной памяти, чем строковое кеширование solve, Основное преимущество unrank заключается в том, что он может возвращать индивидуальное решение из своего порядкового номера вместо того, чтобы производить все решения заданного размера.
Этот код только для Python 3. Достаточно просто преобразовать его для использования в Python 2, вам просто нужно реализовать собственную схему кэширования вместо lru_cache, Вам нужно кэширование, иначе f невыносимо медленный для всех, кроме самых маленьких длин Дейка.
from itertools import product
from functools import lru_cache
# Generate all Dyck words of length 2*num, recursively
# fastest, but not lexicographically ordered
def solve(num, cache = {0: ['']}):
if num not in cache:
cache[num] = ['0%s1%s' % t for i in range(1, num + 1)
for t in product(solve(i - 1), solve(num - i))]
return cache[num]
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# A helper function for `unrank`
# f(i, j) gives the number of paths between (0,0) and (i, j) not crossing
# the diagonal x == y of the grid. Paths consist of horizontal and vertical
# segments only, no diagonals are permitted
@lru_cache(None)
def f(i, j):
if j == 0:
return 1
if j == 1:
return i
#if i < j:
#return 0
if i == j:
return f(i, i - 1)
# 1 < j < i <= n
return f(i - 1, j) + f(i, j - 1)
# Determine the position array of a Dyck word from its rank number,
# The position array gives the indices of the 1s in the word;
# the rank number is the word's index in the lexicographic sequence
# of all Dyck words of length 2n
# Very slow
def unrank(nr, n):
b = [-1]
for i in range(n):
b.append(1 + max(b[-1], 2 * i))
ni = n - i - 1
for j in range(n + i - b[-1], 0, -1):
delta = f(ni, j)
if nr < delta or b[-1] >= n + i:
break
nr -= delta
b[-1] += 1
return b[1:]
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Generate all Dyck word position arrays for words of length 2*n, iteratively
def pos_dyck_words(n):
b = list(range(1, 2 * n, 2))
while True:
yield b
for i in range(n - 2, -1, -1):
if b[i] < n + i:
b[i] += 1
for j in range(i + 1, n - 1):
b[j] = 1 + max(b[j - 1], 2 * j)
break
else:
break
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Convert a position array to a Dyck word
def pos_to_word(b, n, chars='01'):
c0, c1 = chars
word = [c0] * (2 * n)
for i in b:
word[i] = c1
return ''.join(word)
# Some tests
num = 4
print('num: {}, Catalan number: {}'.format(num, f(num, num)))
words = list(solve(num))
words.sort(reverse=True)
print(len(words))
for i, u in enumerate(pos_dyck_words(num)):
v = unrank(i, num)
w = words[i]
ok = u == v and pos_to_word(u, num) == w
print('{:2} {} {} {} {}'.format(i, u, v, w, ok))
print()
num = 10
print('num: {}, Catalan number: {}'.format(num, f(num, num)))
for i, u in enumerate(pos_dyck_words(num)):
v = unrank(i, num)
assert u == v, (i, u, v)
print('ok')
выход
num: 4, Catalan number: 14
14
0 [1, 3, 5, 7] [1, 3, 5, 7] 01010101 True
1 [1, 3, 6, 7] [1, 3, 6, 7] 01010011 True
2 [1, 4, 5, 7] [1, 4, 5, 7] 01001101 True
3 [1, 4, 6, 7] [1, 4, 6, 7] 01001011 True
4 [1, 5, 6, 7] [1, 5, 6, 7] 01000111 True
5 [2, 3, 5, 7] [2, 3, 5, 7] 00110101 True
6 [2, 3, 6, 7] [2, 3, 6, 7] 00110011 True
7 [2, 4, 5, 7] [2, 4, 5, 7] 00101101 True
8 [2, 4, 6, 7] [2, 4, 6, 7] 00101011 True
9 [2, 5, 6, 7] [2, 5, 6, 7] 00100111 True
10 [3, 4, 5, 7] [3, 4, 5, 7] 00011101 True
11 [3, 4, 6, 7] [3, 4, 6, 7] 00011011 True
12 [3, 5, 6, 7] [3, 5, 6, 7] 00010111 True
13 [4, 5, 6, 7] [4, 5, 6, 7] 00001111 True
num: 10, Catalan number: 16796
ok
Я придумал следующий алгоритм, который не является рекурсивным, как того требует OP, но о нем стоит упомянуть, учитывая его непобедимую эффективность.
Как сказано в Ed Guiness пост, строкиNпары правильно подобранных скобок - это представление слова Дика. В другом полезном представлении круглые скобки( а также ) заменены на 1 а также 0соответственно. Следовательно,()()() становится 101010. Последнее также можно рассматривать как двоичное представление (десятичного) числа.42. Таким образом, некоторые целые числа могут представлять строки правильно подобранных пар круглых скобок. Используя это представление, следующий эффективный алгоритм для создания работ Дейка.
Позволять integerбыть любым беззнаковым целочисленным типом C/C++ (или, возможно, членом языков программирования семейства C) длиной до 64 бит. Для данного слова Дайка следующий код возвращает следующее слово Дайка того же размера, если оно существует.
integer next_dyck_word(integer w) {
integer const a = w & -w;
integer const b = w + a;
integer c = w ^ b;
c = (c / a >> 2) + 1;
c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;
return c;
}
Например, если w == 42 (101010 в двоичном, т.е. ()()()) функция возвращает 44 (101100, ()(())). Можно повторять до получения56 (111000, ((()))), которое является максимальным словом Дика для N == 3.
Выше я упомянул непреодолимую эффективность, потому что, что касается генерации одного слова Дайка, этот алгоритм O(1), без циклов и ветвей. Однако в реализации еще есть над чем работать. Действительно, относительно дорогое делениеc / a в теле функции можно исключить, если мы сможем использовать некоторые инструкции по сборке, которые недоступны в C / C++, строго совместимом со стандартом.
Вы могли бы сказать. "Возражение! Я не хочу, чтобыN <= 64". Что ж, мой ответ таков: если вы хотите сгенерировать все работы Дейка, то на практике вы уже привязаны к гораздо меньшему размеру, чем 64. Действительно, количество размерных работ ДейкаN растет факториально с N и для N == 64время, чтобы произвести их все, вероятно, будет больше возраста Вселенной. (Признаюсь, на этот раз я не подсчитывал, но это довольно частая анекдотическая особенность проблем такого рода.)
Я написал подробный документ по алгоритму.
Рекурсивное решение:
import java.util.Scanner;
public class Parentheses
{
static void ParCheck(int left,int right,String str)
{
if (left == 0 && right == 0)
{
System.out.println(str);
}
if (left > 0)
{
ParCheck(left-1, right+1 , str + "(");
}
if (right > 0)
{
ParCheck(left, right-1, str + ")");
}
}
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
System.out.println("Enter the number");
int num=input.nextInt();
String str="";
ParCheck(num,0,str);
}
}