Énumérer tous les arbres binaires avec n nœuds

Étant donné un entier n, énumérer tous les arbres binaires complets possibles avec n nœuds internes. (Les arbres binaires complets ont exactement 2 enfants sur chaque nœud interne). La structure arborescente doit être sortie en tant que parcours de précommande de l'arbre, 1 représentant un nœud interne et 0 représentant un nœud externe (Null).

Voici des exemples pour les premiers n:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

Il s'agit d'un golf de code avec le prix allant au moins de personnages. Les arbres doivent être sortis un par ligne vers stdout. Le programme doit lire n à partir de la ligne de commande ou stdin.

Perl - 125 79 caractères

Le nombre comprend 4 caractères pour les -lnoptions " ". Prend n de stdin.

Nouvelle approche constructive:

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

Former la solution pour n en substituant un nouveau nœud interne ("100") pour chaque feuille ("0"), à son tour, dans chaque arbre de la solution pour n-1.

(Je dois ce concept à d'autres solutions qui utilisent le nœud interne pour remplacer la feuille [100-> 0] pour vérifier les chaînes générées séquentiellement, et je crois avoir vu - après avoir écrit ma réponse basée sur ce concept - ce même 0- > 100 méthode de construction dans l'édition intermédiaire de quelqu'un.)

Approche récursive précédente:

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$_

Récursif non 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;
}

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

S'exécute à partir de la ligne de commande, c'est-à-dire que "php golf.php 1" génère "100".

EDIT: Coupez 4 caractères avec une autre méthode, en construisant les chaînes à partir de 0 plutôt que récursif à partir de $ n. Utilise PHP 5.3 pour l'opérateur ternaire raccourci; sinon, 2 caractères supplémentaires sont nécessaires.

EDIT 2: enregistrement de 4 caractères supplémentaires avec quelques modifications des boucles.

EDIT 3: J'essayais une approche différente et je l'ai finalement obtenue en dessous de l'ancienne méthode.

Tous les arbres peuvent être considérés comme des représentations binaires d'entiers compris entre 4 ^ n (ou 0, lorsque n = 0) et 2 * 4 ^ n. Cette fonction parcourt cette plage et obtient la chaîne binaire de chaque nombre, puis la réduit à plusieurs reprises en remplaçant "100" par "0". Si la chaîne finale est "0", alors c'est un arbre valide, alors sortez-le.

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";}

Ruby, 99 94 92 89 87 caractères

(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}

L'entrée est lue depuis stdin.

> echo 2 | ruby binary_trees.rb
10100
11000

Edit 1: IO modifié (voir les commentaires 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]

Edit 2: algorithme modifié.

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

Edit 3: La version adopte désormais la troisième approche (en utilisant l'idée de migimaru).

Edit 4: Encore deux personnages. Merci à migimaru.

Rubis 1,9 (80) (79)

En utilisant l'approche non récursive et constructive utilisée par DCharness.

EDIT: 1 caractère enregistré.

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

Haskell 122 caractères

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)

Étant donné que l'IO est une partie non triviale du code dans haskell, peut-être que quelqu'un peut utiliser une solution similaire dans une autre langue. Marche essentiellement aléatoire dans un carré du bas à gauche vers le haut à droite en s'arrêtant si la diagonale est traversée. Équivalent à ce qui suit:

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

Golfscript, 60 83

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

J'ai construit un mode golfscript pour Emacs pour y travailler, si quelqu'un est intéressé.