Zlicz wszystkie drzewa binarne z n węzłami

Biorąc pod uwagę liczbę całkowitą n, wylicz wszystkie możliwe pełne drzewa binarne z n węzłów wewnętrznych. (Pełne drzewa binarne mają dokładnie 2 dzieci w każdym węźle wewnętrznym). Struktura drzewa powinna być wyprowadzana jako przejście drzewa przed zamówieniem, przy czym 1 oznacza węzeł wewnętrzny, a 0 reprezentuje węzeł zewnętrzny (Null).

Oto przykłady pierwszych kilku n:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

To jest golf golfowy, w którym nagrodą jest jak najmniej znaków. Drzewa powinny być wyprowadzane po jednym w wierszu na standardowe wyjście. Program powinien czytać n z wiersza poleceń lub stdin.

Perl - 125 79 znaków

Liczba obejmuje 4 znaki dla -lnopcji „ ”. Bierze n od standardowego.

Nowe konstruktywne podejście:

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

Utwórz rozwiązanie dla n, zastępując nowy węzeł wewnętrzny („100”) dla każdego liścia („0”), z kolei w każdym drzewie z rozwiązania dla n-1.

(Zawdzięczam tę koncepcję rozwiązaniom innych, które wykorzystują wewnętrzny węzeł do wstawiania podstawienia [100-> 0] do weryfikacji ciągów generowanych sekwencyjnie i wydaje mi się, że - po napisaniu odpowiedzi opartej na tej koncepcji - to samo 0- > 100 metoda konstrukcji w czyjejś edycji pośredniej).

Poprzednie podejście rekurencyjne:

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

Rekursywny bez golfa:

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)

Działa z wiersza poleceń, tj. „Php golf.php 1” wyprowadza „100”.

EDYCJA: Wytnij 4 znaki alternatywną metodą, budując ciągi od 0 zamiast rekurencji w dół od $ n. Używa PHP 5.3 dla skróconego operatora trójskładnikowego; w przeciwnym razie potrzebne są 2 dodatkowe znaki.

EDYCJA 2: Zapisano 4 kolejne znaki z pewnymi zmianami w pętlach.

EDYCJA 3: Próbowałem innego podejścia i ostatecznie znalazłem go poniżej starej metody.

Wszystkie drzewa można uznać za binarne reprezentacje liczb całkowitych od 4 ^ n (lub 0, gdy n = 0) do 2 * 4 ^ n. Ta funkcja zapętla ten zakres i pobiera ciąg binarny każdej liczby, a następnie wielokrotnie ją zmniejsza, zastępując „100” przez „0”. Jeśli końcowy ciąg to „0”, to jest to prawidłowe drzewo, więc wypisz je.

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 znaków

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

Dane wejściowe są odczytywane ze standardowego wejścia.

> echo 2 | ruby binary_trees.rb
10100
11000

Edycja 1: Zmieniono IO (patrz komentarze Lowjackera)

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]

Edycja 2: Zmieniony algorytm.

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

Edycja 3: Wersja ma teraz trzecie podejście (używając idei migimaru).

Edycja 4: Znów dwie postacie. Dziękuję migimaru.

Rubinowy 1.9 (80) (79)

Korzystanie z nierekurencyjnego, konstruktywnego podejścia stosowanego przez DCharness.

EDYCJA: Zapisano 1 znak.

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

Haskell 122 znaki

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)

Ponieważ IO jest nietrywialną częścią kodu w haskell, być może ktoś może użyć podobnego rozwiązania w innym języku. Zasadniczo losowe spacery po kwadracie od dołu z lewej do prawej u góry, zatrzymywanie się po przekątnej. Odpowiednik następującego:

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

Zbudowałem tryb gry w golfa dla Emacsa do pracy nad tym, jeśli ktoś jest zainteresowany.