Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Trees Made to Order
// 2017/2/25 20:40:17
// http://poj.org/problem?id=1095
// node Trees Made to Order.js
// https://gist.github.com/kanasimi/4f8911cabb8721123a472f60408bd30d
'use strict';
var MAX_NO = 5e8,
// count: Catalan numbers
count = [1],
start_NO = [0];
// initialization
for (var nodes = 0;; nodes++) {
start_NO[nodes + 1] = start_NO[nodes] + count[nodes];
if (start_NO[nodes + 1] >= MAX_NO) break;
// 計算下一個節點數 的 tree數量。
/*
// 較慢的方法,見下方解釋。
var c = 0;
for (var n = 0; n <= nodes; n++) {
c += count[n] * count[nodes - n];
}
count[nodes + 1] = c;
*/
// @see https://en.wikipedia.org/wiki/Catalan_number
count[nodes + 1] = 2 * (2 * nodes + 1) / (nodes + 2) * count[nodes];
}
// count: Catalan numbers
// count: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700
// start_NO: 0,1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,13402697,48760367,178405157,656043857
// count[3] = 5, start_NO[3] = 4: 3個節點的tree共 5個,自 NO 4 開始至 NO (4+ 5-1= 8)
// count[4] = 14, start_NO[4] = 9: 4個節點的tree共14個,自 NO 9 開始至 NO (9+14-1=22)
// count[3] = count[0]*count[2] + count[1]*count[1] + count[2]*count[0]
// count[4] = count[0]*count[3] + count[1]*count[2] + count[2]*count[1] + count[3]*count[0]
// 參見下方 增進理解用 output
function draw(NO, close) {
if (!(NO >= 1)) {
return '';
}
// all node count
var nodes = 1;
// 判別本NO應有幾顆節點nodes
while (!(start_NO[++nodes] > NO)) {}
--nodes;
// 可把下面process.stdout.write(),console.log()打開以增進理解。
if (!close) {
//process.stdout.write('NO ' + NO + ', ' + nodes + ' nodes' + ' + remainder ' + (NO - start_NO[nodes]) + '\t');
}
// 求取remainder
// 提示:n顆節點與n+1顆節點間會按照此remainder的順序按規則排下去。
NO -= start_NO[nodes];
// 判斷 left node count
var left = nodes - 1,
tmp;
// remainder = 左節點NO * 右節點 + 右節點NO
// 看看本remainder為第幾批。 -1: the 1 is root node
while (NO >= (tmp = count[nodes - 1 - left] * count[left])) {
NO -= tmp;
left--;
}
var right_NO = start_NO[nodes - 1 - left] + (NO / count[left] | 0),
left_NO = start_NO[left] + (NO % count[left]);
if (!close) {
//console.log([nodes - 1 - left, left], [right_NO, left_NO]);
}
tmp = draw(right_NO, true) + 'X' + draw(left_NO, true);
return close ? '(' + tmp + ')' : tmp;
}
console.assert(draw(1) === 'X');
console.assert(draw(20) === '((X)X(X))X');
console.assert(draw(31117532) === '(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)');
console.assert(draw(MAX_NO) === '(X(((X(X(X((X(X))X(((X((X)X))X((X)X))X)))))X)X))X(X)');
process.exit();
// 增進理解用
function nodes_of(result) {
if (result >= 0) {
result = draw(result, true);
}
return result.replace(/[^X]+/g, '').length;
}
for (var NO = 1; NO < 80; NO++) {
var result = draw(NO);
// 先看看下一個NO之nodes,若與本NO之nodes不同則加個分隔線。
if (nodes_of(result) !== nodes_of(NO + 1)) {
console.log('-'.repeat(60));
}
}
/*
// 增進理解用 output: 請注意最後一個數(右tree之NO),並對照各NO之數量。
// 例如 NO 9–13 之右tree NO 即為按照 NO 4–8 累增。
// [right nodes, left nodes] [right_NO, left_NO]
NO 1, 1 nodes + remainder 0 [ 0, 0 ] [ 0, 0 ]
------------------------------------------------------------
NO 2, 2 nodes + remainder 0 [ 0, 1 ] [ 0, 1 ]
NO 3, 2 nodes + remainder 1 [ 1, 0 ] [ 1, 0 ]
------------------------------------------------------------
NO 4, 3 nodes + remainder 0 [ 0, 2 ] [ 0, 2 ]
NO 5, 3 nodes + remainder 1 [ 0, 2 ] [ 0, 3 ]
NO 6, 3 nodes + remainder 2 [ 1, 1 ] [ 1, 1 ]
NO 7, 3 nodes + remainder 3 [ 2, 0 ] [ 2, 0 ]
NO 8, 3 nodes + remainder 4 [ 2, 0 ] [ 3, 0 ]
------------------------------------------------------------
NO 9, 4 nodes + remainder 0 [ 0, 3 ] [ 0, 4 ]
NO 10, 4 nodes + remainder 1 [ 0, 3 ] [ 0, 5 ]
NO 11, 4 nodes + remainder 2 [ 0, 3 ] [ 0, 6 ]
NO 12, 4 nodes + remainder 3 [ 0, 3 ] [ 0, 7 ]
NO 13, 4 nodes + remainder 4 [ 0, 3 ] [ 0, 8 ]
NO 14, 4 nodes + remainder 5 [ 1, 2 ] [ 1, 2 ]
NO 15, 4 nodes + remainder 6 [ 1, 2 ] [ 1, 3 ]
NO 16, 4 nodes + remainder 7 [ 2, 1 ] [ 2, 1 ]
NO 17, 4 nodes + remainder 8 [ 2, 1 ] [ 3, 1 ]
NO 18, 4 nodes + remainder 9 [ 3, 0 ] [ 4, 0 ]
NO 19, 4 nodes + remainder 10 [ 3, 0 ] [ 5, 0 ]
NO 20, 4 nodes + remainder 11 [ 3, 0 ] [ 6, 0 ]
NO 21, 4 nodes + remainder 12 [ 3, 0 ] [ 7, 0 ]
NO 22, 4 nodes + remainder 13 [ 3, 0 ] [ 8, 0 ]
------------------------------------------------------------
NO 23, 5 nodes + remainder 0 [ 0, 4 ] [ 0, 9 ]
NO 24, 5 nodes + remainder 1 [ 0, 4 ] [ 0, 10 ]
NO 25, 5 nodes + remainder 2 [ 0, 4 ] [ 0, 11 ]
NO 26, 5 nodes + remainder 3 [ 0, 4 ] [ 0, 12 ]
NO 27, 5 nodes + remainder 4 [ 0, 4 ] [ 0, 13 ]
NO 28, 5 nodes + remainder 5 [ 0, 4 ] [ 0, 14 ]
NO 29, 5 nodes + remainder 6 [ 0, 4 ] [ 0, 15 ]
NO 30, 5 nodes + remainder 7 [ 0, 4 ] [ 0, 16 ]
NO 31, 5 nodes + remainder 8 [ 0, 4 ] [ 0, 17 ]
NO 32, 5 nodes + remainder 9 [ 0, 4 ] [ 0, 18 ]
NO 33, 5 nodes + remainder 10 [ 0, 4 ] [ 0, 19 ]
NO 34, 5 nodes + remainder 11 [ 0, 4 ] [ 0, 20 ]
NO 35, 5 nodes + remainder 12 [ 0, 4 ] [ 0, 21 ]
NO 36, 5 nodes + remainder 13 [ 0, 4 ] [ 0, 22 ]
NO 37, 5 nodes + remainder 14 [ 1, 3 ] [ 1, 4 ]
NO 38, 5 nodes + remainder 15 [ 1, 3 ] [ 1, 5 ]
NO 39, 5 nodes + remainder 16 [ 1, 3 ] [ 1, 6 ]
NO 40, 5 nodes + remainder 17 [ 1, 3 ] [ 1, 7 ]
NO 41, 5 nodes + remainder 18 [ 1, 3 ] [ 1, 8 ]
NO 42, 5 nodes + remainder 19 [ 2, 2 ] [ 2, 2 ]
NO 43, 5 nodes + remainder 20 [ 2, 2 ] [ 2, 3 ]
NO 44, 5 nodes + remainder 21 [ 2, 2 ] [ 3, 2 ]
NO 45, 5 nodes + remainder 22 [ 2, 2 ] [ 3, 3 ]
NO 46, 5 nodes + remainder 23 [ 3, 1 ] [ 4, 1 ]
NO 47, 5 nodes + remainder 24 [ 3, 1 ] [ 5, 1 ]
NO 48, 5 nodes + remainder 25 [ 3, 1 ] [ 6, 1 ]
NO 49, 5 nodes + remainder 26 [ 3, 1 ] [ 7, 1 ]
NO 50, 5 nodes + remainder 27 [ 3, 1 ] [ 8, 1 ]
NO 51, 5 nodes + remainder 28 [ 4, 0 ] [ 9, 0 ]
NO 52, 5 nodes + remainder 29 [ 4, 0 ] [ 10, 0 ]
NO 53, 5 nodes + remainder 30 [ 4, 0 ] [ 11, 0 ]
NO 54, 5 nodes + remainder 31 [ 4, 0 ] [ 12, 0 ]
NO 55, 5 nodes + remainder 32 [ 4, 0 ] [ 13, 0 ]
NO 56, 5 nodes + remainder 33 [ 4, 0 ] [ 14, 0 ]
NO 57, 5 nodes + remainder 34 [ 4, 0 ] [ 15, 0 ]
NO 58, 5 nodes + remainder 35 [ 4, 0 ] [ 16, 0 ]
NO 59, 5 nodes + remainder 36 [ 4, 0 ] [ 17, 0 ]
NO 60, 5 nodes + remainder 37 [ 4, 0 ] [ 18, 0 ]
NO 61, 5 nodes + remainder 38 [ 4, 0 ] [ 19, 0 ]
NO 62, 5 nodes + remainder 39 [ 4, 0 ] [ 20, 0 ]
NO 63, 5 nodes + remainder 40 [ 4, 0 ] [ 21, 0 ]
NO 64, 5 nodes + remainder 41 [ 4, 0 ] [ 22, 0 ]
------------------------------------------------------------
NO 65, 6 nodes + remainder 0 [ 0, 5 ] [ 0, 23 ]
NO 66, 6 nodes + remainder 1 [ 0, 5 ] [ 0, 24 ]
NO 67, 6 nodes + remainder 2 [ 0, 5 ] [ 0, 25 ]
NO 68, 6 nodes + remainder 3 [ 0, 5 ] [ 0, 26 ]
NO 69, 6 nodes + remainder 4 [ 0, 5 ] [ 0, 27 ]
NO 70, 6 nodes + remainder 5 [ 0, 5 ] [ 0, 28 ]
NO 71, 6 nodes + remainder 6 [ 0, 5 ] [ 0, 29 ]
NO 72, 6 nodes + remainder 7 [ 0, 5 ] [ 0, 30 ]
NO 73, 6 nodes + remainder 8 [ 0, 5 ] [ 0, 31 ]
NO 74, 6 nodes + remainder 9 [ 0, 5 ] [ 0, 32 ]
NO 75, 6 nodes + remainder 10 [ 0, 5 ] [ 0, 33 ]
NO 76, 6 nodes + remainder 11 [ 0, 5 ] [ 0, 34 ]
NO 77, 6 nodes + remainder 12 [ 0, 5 ] [ 0, 35 ]
NO 78, 6 nodes + remainder 13 [ 0, 5 ] [ 0, 36 ]
NO 79, 6 nodes + remainder 14 [ 0, 5 ] [ 0, 37 ]
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.