Sebuah pohon adalah terhubung, grafik diarahkan tanpa siklus. Tugas Anda adalah menghitung berapa banyak pohon yang berbeda dengan jumlah simpul tertentu.

Dua pohon dianggap berbeda jika tidak isomorfis . Dua grafik isomorfis jika masing-masing simpul dapat dipasangkan sedemikian rupa sehingga ada tepi antara dua simpul dalam satu grafik jika dan hanya jika ada tepi antara simpul yang dipasangkan dengan simpul-simpul dalam grafik lainnya. Untuk deskripsi yang lebih lengkap, lihat tautan di atas.

Untuk melihat seperti apa semua pohon ukuran 1 hingga 6 yang berbeda, lihat di sini .

Seri yang Anda coba hasilkan adalah A000055 di OEIS.

Pembatasan : Solusi Anda harus dalam rentang menit atau kurang untuk berjalan pada input 6. Ini tidak dimaksudkan untuk menghilangkan algoritme waktu eksponensial, tetapi dimaksudkan untuk menghilangkan algoritme waktu eksponensial ganda, seperti pemaksaan kasar pada semua set edge.

Input: Bilangan bulat non-negatif.

Input dapat dengan cara standar apa pun, termasuk STDIN, parameter baris perintah, input fungsi, dll.

Output: Jumlah pohon yang berbeda dengan simpul sebanyak input.

Output dapat dengan cara standar apa pun, termasuk STDOUT, pengembalian fungsi, dll.

Contoh: 0, 1, 2, 3, 4, 5, 6, 7 harus kembali 1, 1, 1, 1, 2, 3, 6, 11.

Penilaian: Golf kode, berdasarkan byte. Semoga kode terpendek menang!

Celah standar dilarang.

CJam (69 byte)

]qi:X,{1e|,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/z

Demo online

Penjelasan

Ide dasarnya adalah untuk mengimplementasikan fungsi pembangkit yang dijelaskan dalam OEIS. Input adalah kasus khusus yang tidak menyenangkan, tetapi perubahan terakhir yang saya buat akhirnya menghasilkan - 1 untuk kasus itu, jadi z (untuk nilai absolut) merapikannya. Itu trik paling aneh di sini.$0$$-1$$z$

.*:+diulang tiga kali, dan sepertinya itu bisa menghemat byte jika diekstraksi sebagai {.*:+}:F~. Namun, ini rusak dengan case khusus , karena tidak menjalankan loop luar sama sekali.$0$

---

Kami menggunakan fungsi pembangkit tambahan untuk A000081 , yang istilahnya memiliki pengulangan

a[0] = 0
a[1] = 1
For n >= 1, a[n+1] = (sum_{k=1}^n a[n-k+1] * sum_{d|k} d * a[d]) / n

Saya yakin beberapa bahasa memiliki built-in untuk transformasi Möbius terbalik , tetapi CJam tidak; pendekatan terbaik yang pernah ditemukan adalah untuk membangun sebuah array pemetaan d untuk kemudian melakukan perkalian pointwise dengan sebuah menggunakan . Perhatikan bahwa di sini akan lebih mudah untuk telah membangun sebuah mulai dari indeks 1, karena kita ingin divisi menghindari dengan nol bila membuat bobot. Perhatikan juga bahwa jika dua array yang disuplai ke operasi pointwise tidak memiliki panjang yang sama maka nilai dari yang lebih panjang dibiarkan tidak tersentuh: oleh karena itu kita harus mengambil ketentuan k pertama dari$\sum_{d\mid k} d \times a[d]$$d$k % d == 0 ? d : 0$a$.*$a$$k$ atau membuat array bobot naik ke n . Yang terakhir tampaknya lebih pendek. Jadi Möbius terbalik ini mengubah akun untuk$a$$n$N\f{1$%!*}W$.*:+

Jika kita menyebut hasil inverse Möbius transformasi M, kita sekarang memiliki

$$a[n+1] = \frac{1}{n} \sum_{k=1}^n a[n-k+1] \times M[k]$$

$a$$M$$1$$n$$n + 1$$a$

 qi:X,{   ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/

Titik fungsi pembangkit bantu diberikan oleh bagian rumus A000055:

G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2,
where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.

$a$

$$[x = 0] + a[x] + \frac{1}{2}\left(a[x/2] - \sum_{i=0}^n a[i] \times a[n-i]\right)$$

$a[x/2]$$x$1,*X=

0\+$a[0] = 0$$X = 0$W\+$-2a[x] + \sum_{i=0}^n a[i] \times a[n-i]$$2$$a[x]$

Jadi kami sudah menjelaskan

 qi:X,{   ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/

1]$N = 1$

1]qi:X,1>{ ... }/

$X = 0$$a$[-1 1]$0$$[x = 0]$X!+1e|

$a$$1$$N = 0$

]qi:X,{ ... /+}/

jelas memberikan pembagian dengan nol. Tetapi jika kita mencoba

]qi:X,{1e| ... /+}/

lalu bekerja. Kita mendapatkan

             e# Stack: [] 0
1e|          e# Stack: [] 1
,:):N        e# Stack: [] [1]
{            e# We only execute this loop once
  N\f{1$%!*} e#   1 divides 1, so stack: [] [1]
  W$.*       e#   Remember: if the two arrays supplied to the pointwise operation
             e#   are not the same length then the values from the longer one are
             e#   left untouched. Stack: [] [1]
  :+         e#   Fold over a singleton. Stack: [] 1
}%           e# And that was a map, so stack: [] [1]
1$W%.*:+     e# Another [1] [] .*:+, giving the same result: 1
N,/          e# 1 / 1 = 1
+            e# And we append 1 to a giving [1]

yang menghasilkan persis nilai yang kami butuhkan.

$X = 0$$-1$[-1]$(-1 - \frac12(-1 \times -1)) = -1$$0$$1$$-1$$1$z

Pyth, 35 byte

l{m`SmSSMcXdUQk2.pQusm+L,dhHGhHtQ]Y

Demonstrasi.

Program ini dapat dibagi menjadi dua bagian: Pertama, kami membuat semua pohon yang mungkin, kemudian kami menghapus duplikat.

Kode ini menghasilkan pohon: usm+L,dhHGhHtQ]Y. Pohon direpresentasikan sebagai daftar tepi yang disatukan, kira-kira seperti ini:

[0, 1, 0, 2, 2, 3, 1, 4]

Setiap angka berarti sebuah titik, dan setiap dua angka adalah tepi. Itu dibangun dengan berulang kali menambahkan tepi antara setiap simpul yang mungkin ada dan yang baru dibuat, dan menambahkan ini ke setiap pohon yang mungkin dari langkah sebelumnya. Ini menghasilkan semua pohon yang mungkin, karena semua pohon dapat dihasilkan dengan berulang kali menambahkan satu simpul dan satu ujung darinya ke pohon yang ada. Namun, pohon isomorfik akan dibuat.

Selanjutnya, untuk setiap pohon, kami melakukan setiap kemungkinan pelabelan ulang. Ini dilakukan dengan memetakan semua permutasi yang mungkin dari simpul ( m ... .pQ), dan kemudian mentransformasikan pohon dari pemesanan standar ke pemesanan itu, dengan XdUQk. dadalah pohon, kadalah permutasi.

Kemudian, kita memisahkan tepi menjadi daftar terpisah dengan c ... 2, mengurutkan simpul dalam setiap tepi dengan SM, mengurutkan tepi dalam pohon dengan S, memberikan representasi kanonis setiap pohon. Dua langkah ini adalah kodenya mSSMcXdUQk2.pQ.

Sekarang, kami memiliki daftar daftar yang terdiri dari setiap kemungkinan penamaan ulang dari setiap pohon. Kami mengurutkan daftar ini dengan S. Setiap dua pohon isomorfik harus dapat dipindahkan ke dalam kelompok pohon. Dengan menggunakan fakta ini, kami mengonversi setiap daftar menjadi string dengan `, lalu membentuk kumpulan daftar tersebut dengan {, dan menampilkan panjangnya l.