Вот некоторый код, который по сути является компактной версией кода 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)
output
1
()
2
()()
(())
3
()()()
()(())
(())()
(()())
((()))
4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
((()))()
(()()())
(()(()))
((())())
((()()))
(((())))
Вот еще пара функций, производных от псевдокодав статье, на которую ссылается Эд Гиннес: Создание и ранжирование слов Дейка .В этой статье используется индексация на основе 1, но я преобразовал их для соответствия индексации на основе Python 0.
Эти функции работают медленнее, чем функция solve, описанная выше, но они все еще могут быть полезны.pos_dyck_words имеет то преимущество, что оно чисто итеративное.unrank является итеративным, но вызывает рекурсивную вспомогательную функцию f;OTOH, 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')
output
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