Hier einige Code, der außer im Wesentlichen eine kompakte Version von JPvdMerwe des Codes ist, dass es die Liste der Lösungen zurück, anstatt sie zu drucken. Dieser Code funktioniert sowohl Python 2 und 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)
Ausgang
1
()
2
()()
(())
3
()()()
()(())
(())()
(()())
((()))
4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
((()))()
(()()())
(()(()))
((())())
((()()))
(((())))
Hier sind ein paar mehr Funktionen, von dem Pseudo-Code in dem von Ed Guiness verlinkte Artikel gegeben abgeleitet : Generating and ranking of Dyck words. Dieser Artikel verwendet die 1-basierte Indexierung, aber ich habe sie so konvertiert, dass sie der 0-basierten Indizierung von Python entspricht.
Diese Funktionen sind langsamer als die obige Funktion solve
, aber sie können immer noch nützlich sein. pos_dyck_words
hat den Vorteil, dass es rein iterativ ist. unrank
ist iterativ, aber es ruft die rekursive Hilfsfunktion f
auf; OTOH, f
verwendet Caching, daher ist es nicht so langsam, wie es sein könnte, und es werden nur Integer zwischengespeichert, die weniger RAM als das String-Caching von solve
benötigen. Der Hauptvorteil von unrank
ist, dass es eine individuelle Lösung von seiner Indexnummer zurückgeben kann, anstatt alle Lösungen einer gegebenen Größe zu produzieren.
Dieser Code ist nur für Python 3. Es ist einfach genug, um es für die Verwendung von Python 2 zu konvertieren, müssen Sie nur ein eigenes Caching-Schema anstelle von lru_cache
implementieren. Sie tun müssen Caching, sonst f
ist unerträglich langsam für alle außer den kleinsten Dyck Wortlängen.
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')
Ausgang
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
Sie alle Möglichkeiten drucken haben – siva
ist diese Hausaufgaben? –
Ja, wir können. Aber sollten wir? – khachik