algorithm - permutaciones - Permutación válida de paréntesis

formula de combinacion

Question

Posible duplicado:
Solución a un problema recursivo (código kata)

dar un algoritmo para encontrar toda la permutación válida de paréntesis para n dado por ejemplo:

for n=3, O/P should be
{}{}{} 
{{{}}}
{{}}{} 
{}{{}} 
{{}{}}

Answer 1

Visión general del problema

Este es un problema combinatorio clásico que se manifiesta de muchas maneras diferentes. Estos problemas son esencialmente idénticos:

• Generando todas las formas posibles para equilibrar N pares de paréntesis (es decir, este problema)
• Generando todas las formas posibles de aplicar un operador binario a N+1 factores
• Generar todos los árboles binarios completos con N+1 hojas
• Muchos otros...

Ver también

• Wikipedia / número catalán
• Enciclopedia en línea de secuencias enteras / A000108

Una solución recursiva directa

Aquí hay un algoritmo recursivo simple para resolver este problema en Java:

public class Parenthesis {
    static void brackets(int openStock, int closeStock, String s) {
        if (openStock == 0 && closeStock == 0) {
            System.out.println(s);
        }
        if (openStock > 0) {
            brackets(openStock-1, closeStock+1, s + "<");
        }
        if (closeStock > 0) {
            brackets(openStock, closeStock-1, s + ">");
        }
    }
    public static void main(String[] args) {
        brackets(3, 0, "");
    }
}

Las impresiones de arriba ( como se ve en ideone.com ):

<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

Esencialmente hacemos un seguimiento de cuántos paréntesis de apertura y cierre están "disponibles" para que los usemos mientras construimos la cadena recursivamente.

• Si no hay nada en stock, la cadena está completamente construida y solo puede imprimirla
• Si hay un paréntesis abierto disponible en stock, intente y agréguelo.
  • Ahora tiene un paréntesis abierto menos , pero un paréntesis más cercano para equilibrarlo
• Si hay un paréntesis cercano disponible en stock, intente y agréguelo.
  • Ahora tienes uno menos paréntesis

Tenga en cuenta que si intercambia el orden de la recursión de manera que intente agregar un paréntesis de cierre antes de intentar agregar un paréntesis abierto, ¡simplemente obtendrá la misma lista de paréntesis equilibrados, pero en orden inverso! ( ver en ideone.com ).

Una variante "optimizada"

La solución anterior es muy sencilla e instructiva, pero se puede optimizar aún más.

La optimización más importante está en el aspecto de construcción de cuerdas. Aunque parece una simple concatenación de cadenas en la superficie, la solución anterior en realidad tiene un componente de construcción de cadenas O(N^2) "oculto" (porque concatenar un carácter a una String inmutable de longitud N es una operación O(N) ) . En general, optimizamos esto utilizando un StringBuilder mutable, pero en este caso particular también podemos simplemente usar un char[] fijo char[] y una variable de index .

También podemos optimizar simplificando el árbol de recursión. En lugar de recurrir "en ambos sentidos" como en la solución original, podemos recurrir "en una dirección" y hacer "en otra dirección" de forma iterativa.

A continuación, hemos hecho ambas optimizaciones, usando char[] e index lugar de String , y recurriendo solo para agregar paréntesis abiertos, agregando cerrar paréntesis de manera iterativa: (ver también en ideone.com)

public class Parenthesis2 {
    public static void main(String[] args) {
        brackets(4);
    }
    static void brackets(final int N) {
        brackets(N, 0, 0, new char[N * 2]);
    }
    static void brackets(int openStock, int closeStock, int index, char[] arr) {
        while (closeStock >= 0) {
            if (openStock > 0) {
                arr[index] = ''<'';
                brackets(openStock-1, closeStock+1, index+1, arr);
            }
            if (closeStock-- > 0) {
                arr[index++] = ''>'';
                if (index == arr.length) {
                    System.out.println(arr);
                }
            }
        }
    }
}

La lógica de recursión es menos obvia ahora, pero las dos técnicas de optimización son instructivas.

Preguntas relacionadas

• Verificar cadena tiene paréntesis equilibrados
• Recursión básica, verificar paréntesis equilibrado
• La cantidad posible de árboles de búsqueda binaria que pueden crearse con N teclas viene dada por el N ° número catalán. ¿Por qué?

Answer 2

Eric Lippert blogueó recientemente sobre esto en su artículo Every Tree There Is . El artículo se refiere al código escrito en el artículo anterior. Todo árbol binario existe .

Si puede enumerar todos los árboles binarios, entonces puede enumerar todas las soluciones a docenas de problemas equivalentes diferentes.

Answer 3

Si bien no es un algoritmo real, un buen punto de partida son los números catalanes:

Referencia

• http://en.wikipedia.org/wiki/Catalan_number

Answer 4

Una solución no recursiva en Python:

#! /usr/bin/python

def valid(state,N):
    cnt=0
    for i in xrange(N):
        if cnt<0:
            return False
        if (state&(1<<i)):
            cnt+=1
        else:
            cnt-=1
    return (cnt==0)

def make_string(state,N):
    ret=""
    for i in xrange(N):
        if state&(1<<i):
            ret+=''{''
        else:
            ret+=''}''
    return ret

def all_permuts(N):
    N*=2
    return [make_string(state,N) for state in xrange(1<<N) if valid(state,N)]

if __name__==''__main__'':
    print "/n".join(all_permuts(3))

Esto básicamente examina la representación binaria de cada número en [0,2 ^ n), tratando un ''1'' como ''{'' y un ''0'' como un ''}'' y luego filtra solo aquellos que están correctamente equilibrados.