Hitung semua pohon biner dengan n node

10

Dengan bilangan bulat n, sebutkan semua kemungkinan pohon biner penuh dengan n simpul internal. (Pohon biner penuh memiliki tepat 2 anak di setiap simpul internal). Struktur pohon harus berupa output sebagai traversal pre-order dari pohon dengan 1 mewakili simpul internal, dan 0 mewakili simpul eksternal (Null).

Berikut adalah contoh untuk beberapa n pertama:

0:
0

1:
100

2:
11000
10100

3:
1110000
1101000
1100100
1011000
1010100

Ini adalah kode golf dengan hadiah mencapai karakter paling sedikit. Pohon-pohon harus menghasilkan satu per baris ke stdout. Program harus membaca n dari commandline atau stdin.

Kyle Butt
sumber
Saya sedang memikirkan masalah itu ketika saya mencoba membuat sistem penulisan seperti labirin
Ming-Tang
Apa batas waktu standar sebelum mendeklarasikan solusi?
Kyle Butt
Apakah ada minat untuk melakukan sedikit variasi dari masalah ini, di mana output harus dipesan, dan streaming?
Kyle Butt
@Kyle Butt Hanya pendapat saya, tapi saya tidak berpikir saya akan tertarik. Bagi saya, bagian dari kesenangan dengan masalah ini adalah mencoba pendekatan alternatif, dan membutuhkan urutan tertentu kemungkinan akan membatasi jumlah algoritma yang layak.
migimaru

Jawaban:

3

Perl - 125 79 karakter

Hitung termasuk 4 karakter untuk -lnopsi " ". Mengambil n dari stdin.

Pendekatan konstruktif baru:

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

Bentuk solusi untuk n dengan mengganti simpul internal baru ("100") untuk setiap daun ("0"), pada gilirannya, di setiap pohon dari solusi untuk n-1.

(Saya berutang konsep ini kepada solusi orang lain yang menggunakan subtitusi internal node to leaf [100-> 0] untuk memverifikasi string yang dihasilkan secara berurutan, dan saya yakin saya melihat - setelah menulis jawaban saya berdasarkan konsep itu - ini sama dengan 0 - > 100 metode konstruksi dalam pengeditan menengah seseorang.)

Pendekatan rekursif sebelumnya:

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

Berubah tak rekursif:

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

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

Berjalan dari baris perintah, yaitu "php golf.php 1" menghasilkan "100".

Suntingan: Potong 4 karakter dengan metode alternatif, susun string dari 0 daripada berulang dari $ n. Menggunakan PHP 5.3 untuk operator ternary yang dipersingkat; jika tidak, diperlukan 2 karakter lagi.

EDIT 2: Menyimpan 4 karakter lagi dengan beberapa perubahan pada loop.

EDIT 3: Saya sedang mencoba pendekatan yang berbeda dan akhirnya saya mendapatkannya di bawah metode lama.

Semua pohon dapat dianggap sebagai representasi biner dari bilangan bulat antara 4 ^ n (atau 0, ketika n = 0) dan 2 * 4 ^ n. Fungsi ini loop melalui rentang itu, dan mendapatkan string biner dari setiap angka, kemudian berulang kali menguranginya dengan mengganti "100" dengan "0". Jika string terakhir adalah "0", maka itu adalah pohon yang valid, jadi hasilkan.

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

Ruby, 99 94 92 89 87 karakter

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

Input dibaca dari stdin.

> echo 2 | ruby binary_trees.rb
10100
11000

Sunting 1: IO yang Diubah (lihat komentar 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]

Sunting 2: Algoritma berubah.

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

Sunting 3: Versi sekarang menggunakan pendekatan ketiga (menggunakan ide migimaru).

Sunting 4: Lagi dua karakter. Terima kasih untuk migimaru.

Howard
sumber
Akan lebih pendek satu karakter untuk menerima input dari stdin.
Lowjacker
Juga, Anda tidak perlu *?\n, karena putsmencetak setiap elemen dari array di barisnya sendiri.
Lowjacker
@ Lowjacker Terima kasih.
Howard
Saya baru saja mulai mencoba mempelajari Ruby, tetapi saya pikir Anda dapat menyimpan karakter dengan menggunakan 0while alih-alih {} while. Setidaknya itu berfungsi di NetBeans.
migimaru
Juga, sub! sudah cukup di sini alih-alih gsub !, jadi itu karakter lain yang bisa Anda selamatkan.
migimaru
1

Ruby 1.9 (80) (79)

Menggunakan pendekatan non-rekursif dan konstruktif yang digunakan oleh DCharness.

EDIT: Disimpan 1 karakter.

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

Haskell 122 karakter

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)

Karena IO adalah bagian non-sepele dari kode di haskell, mungkin seseorang dapat menggunakan solusi serupa dalam bahasa lain. Intinya acak berjalan di kotak dari kiri bawah ke kanan berhenti jika diagonal disilangkan. Setara dengan yang berikut:

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
sumber
Perhatikan bahwa saya tidak bermaksud menerima ini sebagai jawabannya, hanya berpikir saya akan melemparkan milik saya di luar sana.
Kyle Butt
0

Golfscript, 60 83

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

Saya membangun mode skrip golf untuk Emacs untuk mengerjakan ini, jika ada yang tertarik.

Jesse Millikan
sumber