Algorithme récursif pour les paires de parenthèses

Question

J'essaie de répondre à la question suivante: «Implémenter un algorithme pour imprimer toutes les combinaisons valides (c'est-à-dire correctement ouvertes et fermées) de paires de parenthèses. La réponse dit: «Notre première pensée pourrait être d'appliquer une approche récursive, où nous construisons la solution pour f (n) en ajoutant des paires de parenthèses à f (n - 1). une paire de parenthèses à l'intérieur de chaque paire de parenthèses existante, ainsi qu'une au début de la chaîne. "

J'ai du mal à comprendre comment nous pouvons garantir que l'insertion d'une paire de parenthèses à l'intérieur de chaque paire de parenthèses existante, ainsi qu'une autre au début de la chaîne, créera toutes les solutions possibles. Comment savons-nous que cela ne produira pas de solutions en double ou laissera de bonnes solutions? Quelqu'un pourrait-il expliquer?

(Source des citations: Cracking the Interview de codage)

Answer 1

L'approche que vous décrit fonctionne bien pour f (1) et f (2). Pour n> 2, il n'en manquera aucun, mais il générera des doublons.

Pour f (3), il s'agit de la génération de doublons. En se basant sur f (2), vous avez les 2 solutions de "()()" et "(())". Lorsque vous insérez la parenthèse suivant cet algorithme, vous finissez par les deux solutions générant "() (())". Vous vous retrouvez avec 6 solutions de f (3) au lieu des 5 réelles à cause de ce double.

Si vous appliquez l'algorithme à f (5), il génère 33 solutions totales de f (1) à f (5). Il ne devrait y avoir que 22 solutions, donc vous obtenez 10 doublons là-bas.

Il existe une solution récursive très courante qui implique le comptage de plusieurs parenthèses ouvrantes et fermantes. La meilleure explication que je l'ai vu est à https://anonymouscoders.wordpress.com/2015/06/16/all-balanced-permutation-of-number-of-given-parentheses/

Voici un exemple de l'une des solutions en C:

// Source: http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/ 
# include<stdio.h> 
# define MAX_SIZE 100 

void _printParenthesis(int pos, int n, int open, int close); 

/* Wrapper over _printParenthesis()*/ 
void printParenthesis(int n) 
{ 
    if(n > 0) 
    _printParenthesis(0, n, 0, 0); 
    return; 
}  

void _printParenthesis(int pos, int n, int open, int close) 
{ 
    static char str[MAX_SIZE];  

    if(close == n) 
    { 
    printf("%s \n", str); 
    return; 
    } 
    else 
    { 
    if(open > close) { 
     str[pos] = '}'; 
     _printParenthesis(pos+1, n, open, close+1); 
    } 
    if(open < n) { 
     str[pos] = '{'; 
     _printParenthesis(pos+1, n, open+1, close); 
    } 
    } 
} 

/* driver program to test above functions */ 
int main() 
{ 
    int n = 4; 
    printParenthesis(n); 
    getchar(); 
    return 0; 
} 

Pour référence, voici une version C# je l'ai fait pour votre algorithme fourni:

// Initial funtion call 
void f(int n) 
{ 
    f(1, n, ""); 
} 

// Recursive call 
void f(int n, int max, string output) 
{ 
    for (int i = 0; i < output.Length; i++) 
    { 
     if (output[i] == '(') 
     { 
      var inserted = output.Insert(i + 1, "()"); 
      Console.WriteLine(inserted); 
      if (n < max) 
       f(n + 1, max, inserted); 
     } 
    } 

    // Pre-pend parens 
    output = "()" + output; 
    Console.WriteLine(output); 
    if (n < max) 
     f(n + 1, max, output); 
} 

f(4); 

Lien: https://dotnetfiddle.net/GR5l6C