Enumerar todos los árboles binarios con n nodos

10

Dado un número entero n, enumere todos los árboles binarios completos posibles con n nodos internos. (Los árboles binarios completos tienen exactamente 2 hijos en cada nodo interno). La estructura de árbol se debe generar como un recorrido de preorden del árbol, donde 1 representa un nodo interno y 0 representa un nodo externo (Nulo).

Aquí hay ejemplos para los primeros n:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

Este es un código de golf con el premio a la menor cantidad de personajes. Los árboles deben salir uno por línea a stdout. El programa debería leer n desde la línea de comandos o stdin.

Kyle Butt
fuente
Estaba pensando en ese problema cuando intentaba hacer un sistema de escritura similar a un laberinto
Ming-Tang
¿Cuál es el plazo estándar antes de declarar una solución?
Kyle Butt
¿Habría algún interés en hacer una ligera variación de este problema, donde se requería ordenar la salida y transmitir?
Kyle Butt
@Kyle Butt Solo mi opinión, pero no creo que me interese. Para mí, parte de la diversión con estos problemas es probar enfoques alternativos, y requerir un cierto orden probablemente limitaría la cantidad de algoritmos viables.
migimaru

Respuestas:

3

Perl - 125 79 caracteres

El recuento incluye 4 caracteres para las " -ln" opciones. Toma n de stdin.

Nuevo enfoque constructivo:

@a=0;map{%a=();map{$a{"$`100$'"}=1while/0/g;}@a;@a=keys%a}1..$_;print for@a

Forme la solución para n sustituyendo un nuevo nodo interno ("100") para cada hoja ("0"), a su vez, en cada árbol de la solución para n-1.

(Debo este concepto a las soluciones de otros que usan el nodo interno para hojear la sustitución [100-> 0] para verificar cadenas generadas secuencialmente, y creo que vi, después de escribir mi respuesta basada en ese concepto, este mismo 0- > 100 método de construcción en la edición intermedia de alguien.)

Enfoque recursivo previo:

sub t{my$n=shift;if($n){--$n;for$R(0..$n){for$r(t($R)){for$l(t($n-$R)){push@_,"1$l$r"}}}}else{push@_,"0"}@_}print for t$_

Recursivo sin golf:

sub tree {
  my ($n) = @_;
  my @result = ();
  if ( $n ) {
    for $right_count ( 0 .. $n-1 ) {
      for $right ( tree( $right_count ) ) {
        for $left ( tree( ($n-1) - $right_count ) ) {
          push @result, "1$left$right";
        }
      }
    }
  }
  else {
    push @result, "0";
  }
  return @result;
}
foreach $tree ( tree($_) ) {
  print $tree;
}
DCharness
fuente
2

PHP (142) (138) (134) (113)

Se ejecuta desde la línea de comando, es decir, "php golf.php 1" genera "100".

EDITAR: Corte 4 caracteres con un método alternativo, construyendo las cadenas desde 0 en lugar de recurrir desde $ n. Utiliza PHP 5.3 para el operador ternario acortado; de lo contrario, se necesitan 2 caracteres más.

EDIT 2: guardado 4 caracteres más con algunos cambios en los bucles.

EDITAR 3: estaba probando un enfoque diferente y finalmente lo obtuve por debajo del método anterior.

Todos los árboles pueden considerarse representaciones binarias de enteros entre 4 ^ n (o 0, cuando n = 0) y 2 * 4 ^ n. Esta función recorre ese rango y obtiene la cadena binaria de cada número, luego la reduce repetidamente reemplazando "100" por "0". Si la cadena final es "0", entonces es un árbol válido, así que escríbalo.

for($i=$p=pow(4,$argv[1])-1;$i<=2*$p;){$s=$d=decbin($i++);while($o!=$s=str_replace(100,0,$o=$s));echo$s?:"$d\n";}
migimaru
fuente
2

Ruby, 99 94 92 89 87 caracteres

(n=4**gets.to_i).times{|i|s=(n+i-1).to_s 2;t=s*1;0while s.sub!'100',?0;puts t if s==?0}

La entrada se lee desde stdin.

> echo 2 | ruby binary_trees.rb
10100
11000

Edición 1: IO modificada (ver comentarios de Lowjacker)

b=->n{n==0?[?0]:(k=[];n.times{|z|b[z].product(b[n-1-z]){|l|k<<=?1+l*''}};k)}
puts b[gets.to_i]

Edición 2: Algoritmo cambiado.

b=->n{n==0?[?0]:(k=[];b[n-1].map{|s|s.gsub(/0/){k<<=$`+'100'+$'}};k.uniq)}
puts b[gets.to_i]

Edición 3: La versión ahora toma el tercer enfoque (usando la idea de migimaru).

Edición 4: de nuevo dos personajes. Gracias a migimaru.

Howard
fuente
Sería un carácter más corto para aceptar la entrada de stdin.
Lowjacker
Además, no necesita el *?\n, porque putsimprime cada elemento de la matriz en su propia línea.
Lowjacker
@Lowjacker Gracias.
Howard
Acabo de empezar a tratar de aprender Ruby, pero creo que puedes guardar un personaje usando 0 while en lugar de {} while. Al menos funciona en NetBeans.
migimaru
Además, sub! es suficiente aquí en lugar de gsub !, así que ese es otro personaje que podrías guardar.
migimaru
1

Rubí 1.9 (80) (79)

Utilizando el enfoque constructivo no recursivo utilizado por DCharness.

EDITAR: Guardado 1 personaje.

s=*?0;gets.to_i.times{s.map!{|x|x.gsub(?0).map{$`+'100'+$'}}.flatten!}
puts s&s
migimaru
fuente
0

Haskell 122 caracteres

main=do n<-readLn;mapM putStrLn$g n n
g 0 0=[['0']]
g u r|r<u||u<0=[]
g u r=do s<-[1,0];map((toEnum$s+48):)$g(u-s)(r-1+s)

Dado que el IO es una parte no trivial del código en Haskell, tal vez alguien pueda usar una solución similar en otro idioma. Esencialmente camina al azar en un cuadrado de abajo a la izquierda a la derecha y se detiene si se cruza la diagonal. Equivalente a lo siguiente:

module BinTreeEnum where

import Data.List
import Data.Monoid

data TStruct = NonEmpty | Empty deriving (Enum, Show)
type TreeDef = [TStruct]

printTStruct :: TStruct -> Char
printTStruct NonEmpty = '1'
printTStruct Empty = '0'

printTreeDef :: TreeDef -> String
printTreeDef = map printTStruct

enumBinTrees :: Int -> [TreeDef]
enumBinTrees n = enumBinTrees' n n where
  enumBinTrees' ups rights | rights < ups = mempty
  enumBinTrees' 0   rights = return (replicate (rights+1) Empty)
  enumBinTrees' ups rights = do
    step <- enumFrom (toEnum 0)
    let suffixes =
          case step of
            NonEmpty -> enumBinTrees' (ups - 1) rights
            Empty -> enumBinTrees' ups (rights - 1)
    suffix <- suffixes
    return (step:suffix)

mainExample = do
  print $ map printTreeDef $ enumBinTrees 4
Kyle Butt
fuente
Tenga en cuenta que no tengo la intención de aceptar esto como la respuesta, solo pensé en tirar el mío por ahí.
Kyle Butt
0

Golfscript, 60 83

~[1,]\,{;{[:l.,,]zip{({;}{~:a;[l a<~1 0.l a)>~]}if}/}%}/{n}%

Construí un modo golfscript para Emacs para trabajar en esto, si alguien está interesado.

Jesse Millikan
fuente