2010-11-30 9 views
2

Wie können wir alle Möglichkeiten auf geschweiften Klammern generieren?Rezidivansatz: Wie können wir alle Möglichkeiten für Zahnspangen generieren?

N Wert hat uns gegeben und wir müssen alle Möglichkeiten generieren.

Beispiele:

1) wenn N == 1, dann ist nur eine Möglichkeit().

2) wenn N == 2, dann Möglichkeiten sind (()),()()

3) wenn N == 3, dann Möglichkeiten sind ((())), (())(),()()(),() (()) ...

Hinweis: linke und rechte Klammern sollten übereinstimmen. Ich meine) (ist ungültig für die N == 1

können wir dieses Problem lösen, indem Wiederholung Ansatz?

+0

Sie alle Möglichkeiten drucken haben – siva

+3

ist diese Hausaufgaben? –

+3

Ja, wir können. Aber sollten wir? – khachik

Antwort

2

Versuch für katalanische Zahlen Google

3

Für ein gegebenes N müssen wir immer beginnen mit . eine offene Klammer betrachten wir nun, wo es entsprechende schließende Klammer ist es wie wie (()) für N=2 in ()() oder am Ende in der Mitte sein kann

betrachten wir nun N=3:..

Es kann am Ende sein: (()()) und ((())).

Oder in der Mitte: ()(()) und ()()() wo es in Position 2 ist. Dann kann es auch in Position 4 sein: (())().

Jetzt können wir die 2 Fälle im Wesentlichen kombinieren, indem wir den Fall realisieren, in dem die schließende Klammer am Ende die gleiche ist wie in der Mitte, aber mit allen Möglichkeiten für N = 0 am Ende hinzugefügt.

Jetzt zu lösen, können Sie alle Möglichkeiten für n zwischen der Anfangs- und Endstütze ausarbeiten und in ähnlicher Weise können Sie alle Möglichkeiten für m nach der Endklammer ausarbeiten. (Hinweis m+n+1 = N) Dann können Sie einfach alle möglichen Kombinationen kombinieren, sie an Ihre Liste der Möglichkeiten anhängen und zum nächsten möglichen Ort für die Endklammer gehen.

gerade einen leichten Fehler gewarnt werden, mit dieser Art von Problemen zu machen, ist es, alle Möglichkeiten für i und für N-i zu finden und sie nur verbinden, sondern diese für N=3 Doppel ()()() es zählen würde zweimal oder zumindest drucken.

Hier finden Sie einige Python 2.x-Code, der das Problem löst:

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] 
+0

Dies ist keine Hausaufgaben und ich bin kein Schuljunge. Das ist Interviewfrage. – siva

+0

@siva Meine Entschuldigung dann :) – JPvdMerwe

+0

FWIW, ich habe gerade Ihren Code in einer kompakteren Form neu geschrieben und es Python 3 kompatibel gemacht. –

4

Aus Wikipedia -

Ein Dyck Wort ist eine Zeichenkette, die aus n X und n Y ist, so dass kein Anfangs Segment der Zeichenfolge hat mehr Y als X (siehe auch Dyck-Sprache).Zum Beispiel Im folgenden sind die Dyck Wörter der Länge 6:

XXXYYY  XYXXYY  XYXYXY  XXYYXY  XXYXYY. 

Re-Interpretation des Symbols X als offene Klammer und Y als schließende Klammer, Cn die Anzahl von Ausdrücken zählt, die n-Paare von Klammern, die richtig aufeinander abgestimmt sind:

((())) ()(()) ()()()  (())()  (()()) 

Siehe auch http://www.acta.sapientia.ro/acta-info/C1-1/info1-9.pdf

Zusammenfassung. Ein neuer Algorithmus zum Erzeugen aller Dyck-Wörter wird präsentiert, , der in Rangfolge- und Nichtranking-Dyck-Wörtern verwendet wird. Wir betonen die Wichtigkeit der Verwendung von Dyck-Wörtern bei der Codierung von Objekten im Zusammenhang mit katalanischen Zahlen. Als Konsequenz der im Ranking-Algorithmus verwendeten Formeln können wir eine rekursive Formel für die n-te katalanische Zahl erhalten.

+0

Netter Link. FWIW, ich habe gerade einen Teil des Pseudocodes in diesem Artikel in Python implementiert. –

1

rekursive Lösung:

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

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 
+0

FWIW, ich schrieb diese Antwort als Antwort auf eine neue Frage, die als ein Duplikat geschlossen wurde. –

Verwandte Themen