Zählen Sie alle Binärbäume mit n Knoten auf

10

Zählen Sie bei einer Ganzzahl n alle möglichen vollständigen Binärbäume mit n internen Knoten auf. (Vollständige Binärbäume haben genau 2 Kinder auf jedem internen Knoten). Die Baumstruktur sollte als Vorbestellungsdurchquerung des Baums ausgegeben werden, wobei 1 einen internen Knoten und 0 einen externen Knoten (Null) darstellt.

Hier sind Beispiele für die ersten paar n:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

Dies ist ein Code-Golf, bei dem der Preis an die wenigsten Charaktere geht. Die Bäume sollten eine pro Zeile an stdout ausgegeben werden. Das Programm sollte n von der Kommandozeile oder stdin lesen.

Kyle Butt
quelle
Ich habe über dieses Problem nachgedacht, als ich versuchte, ein labyrinthartiges Schriftsystem zu entwickeln
Ming-Tang,
Was ist die Standardfrist, bevor eine Lösung deklariert wird?
Kyle Butt
Besteht Interesse daran, dieses Problem geringfügig zu ändern, wenn die Ausgabe bestellt werden muss, und zu streamen?
Kyle Butt
@ Kyle Butt Nur meine Meinung, aber ich glaube nicht, dass ich interessiert wäre. Für mich besteht ein Teil des Spaßes bei diesen Problemen darin, alternative Ansätze auszuprobieren, und das Erfordernis einer bestimmten Reihenfolge würde wahrscheinlich die Anzahl praktikabler Algorithmen begrenzen.
Migimaru

Antworten:

3

Perl - 125 79 Zeichen

Die Anzahl enthält 4 Zeichen für " -ln" Optionen. Nimmt n von stdin.

Neuer konstruktiver Ansatz:

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

Bilden Sie die Lösung für n, indem Sie für jedes Blatt ("0") in jedem Baum aus der Lösung für n-1 einen neuen internen Knoten ("100") einsetzen.

(Ich verdanke dieses Konzept den Lösungen anderer, die den internen Knoten verwenden, um [100-> 0] als Ersatz für die Überprüfung von sequentiell generierten Zeichenfolgen zu verwenden, und ich glaube, ich habe - nachdem ich meine Antwort basierend auf diesem Konzept geschrieben habe - dieselbe 0- gesehen. > 100 Konstruktionsmethode in einer Zwischenbearbeitung.)

Bisheriger rekursiver Ansatz:

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

Rekursiv ungolfed:

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
quelle
2

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

Läuft über die Befehlszeile, dh "php golf.php 1" gibt "100" aus.

BEARBEITEN: Schneiden Sie 4 Zeichen mit einer alternativen Methode aus und bauen Sie die Zeichenfolgen von 0 auf, anstatt von $ n aus zu rekursieren. Verwendet PHP 5.3 für den verkürzten ternären Operator. Andernfalls werden 2 weitere Zeichen benötigt.

BEARBEITEN 2: 4 weitere Zeichen mit einigen Änderungen an den Schleifen gespeichert.

EDIT 3: Ich habe einen anderen Ansatz ausprobiert und ihn schließlich unter die alte Methode gebracht.

Alle Bäume können als binäre Darstellungen von ganzen Zahlen zwischen 4 ^ n (oder 0, wenn n = 0) und 2 * 4 ^ n betrachtet werden. Diese Funktion durchläuft diesen Bereich und ruft die Binärzeichenfolge jeder Zahl ab. Anschließend wird sie wiederholt reduziert, indem "100" durch "0" ersetzt wird. Wenn die letzte Zeichenfolge "0" ist, handelt es sich um einen gültigen Baum. Geben Sie ihn daher aus.

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
quelle
2

Ruby, 99 94 92 89 87 Zeichen

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

Die Eingabe wird von stdin gelesen.

> echo 2 | ruby binary_trees.rb
10100
11000

Bearbeiten 1: Geänderte E / A (siehe Kommentare von 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: Geänderter Algorithmus.

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: Die Version verfolgt nun den dritten Ansatz (unter Verwendung der Idee von Migimaru).

Edit 4: Wieder zwei Zeichen. Vielen Dank an Migimaru.

Howard
quelle
Es wäre ein Zeichen kürzer, Eingaben von stdin zu akzeptieren.
Lowjacker
Außerdem benötigen Sie das nicht *?\n, da putsjedes Element des Arrays in einer eigenen Zeile gedruckt wird.
Lowjacker
@ Lowjacker Danke.
Howard
Ich habe gerade angefangen, Ruby zu lernen, aber ich denke, Sie können einen Charakter speichern, indem Sie 0while anstelle von {} while verwenden. Zumindest funktioniert es in NetBeans.
Migimaru
Auch sub! ist hier ausreichend anstelle von gsub!, das ist also ein weiterer Charakter, den Sie speichern könnten.
Migimaru
1

Ruby 1,9 (80) (79)

Verwendung des nicht rekursiven, konstruktiven Ansatzes von DCharness.

BEARBEITEN: 1 Zeichen gespeichert.

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

Haskell 122 Zeichen

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)

Da das E / A ein nicht trivialer Teil des Codes in haskell ist, kann möglicherweise jemand eine ähnliche Lösung in einer anderen Sprache verwenden. Im Wesentlichen zufällige Spaziergänge in einem Quadrat von links unten nach rechts oben, wobei angehalten wird, wenn die Diagonale gekreuzt wird. Entspricht dem Folgenden:

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
quelle
Beachten Sie, dass ich dies nicht als Antwort akzeptieren möchte, sondern nur dachte, ich würde meine da rauswerfen.
Kyle Butt
0

Golfscript, 60 83

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

Ich habe einen Golfscript-Modus für Emacs erstellt, um daran zu arbeiten, falls jemand interessiert ist.

Jesse Millikan
quelle