List rooted trees: Difference between revisions
Content added Content deleted
(add Julia example) |
|||
| Line 913: | Line 913: | ||
</pre> |
</pre> |
||
The bag <code>bag(bag(bag()), bag()(2))</code> coresponds with <code>((())()())</code>. There are two independent ways how we can get it by nesting 4 bags. |
The bag <code>bag(bag(bag()), bag()(2))</code> coresponds with <code>((())()())</code>. There are two independent ways how we can get it by nesting 4 bags. |
||
=={{header|Phix}}== |
|||
{{trans|Go}} |
|||
<lang Phix>atom t0 = time() |
|||
sequence list = {1}, |
|||
offset = repeat(0,32) |
|||
offset[1..2] = 1 |
|||
function show(integer t, l) |
|||
string res = repeat('?',l) |
|||
integer level = 0 |
|||
for i=l to 1 by -1 do |
|||
integer r2 = remainder(t,2) |
|||
res[i] = "[}(]{)"[mod(level-r2,6)+1] |
|||
level += r2*4-2 |
|||
t = floor(t/2) |
|||
end for |
|||
if level!=0 then ?9/0 end if |
|||
return res |
|||
end function |
|||
procedure listTrees(integer n) |
|||
for i:=offset[n+1]+1 to offset[n+2] do |
|||
printf(1,"%s\n",{show(list[i], n*2)}) |
|||
end for |
|||
end procedure |
|||
procedure assemble(atom t, integer n, sl, pos, rem) |
|||
-- |
|||
-- assemble tree from subtrees |
|||
-- t: assembled parts so far |
|||
-- n: length of tree we want to make |
|||
-- sl: length of subtree we are looking at |
|||
-- pos: offset of subtree we are looking at |
|||
-- rem: remaining length to be put together |
|||
-- |
|||
if rem == 0 then |
|||
list = append(list, t*2+1) |
|||
else |
|||
if sl>rem then -- need smaller sub-trees |
|||
sl = rem |
|||
pos = offset[sl+1] |
|||
elsif pos>=offset[sl+2] then |
|||
-- used up sl-trees, try smaller ones |
|||
if sl == 1 then return end if |
|||
pos = offset[sl] |
|||
sl -= 1 |
|||
end if |
|||
atom u = or_bits(t*power(2,2*sl),list[pos+1]) |
|||
assemble(u, n, sl, pos, rem-sl) |
|||
assemble(t, n, sl, pos+1, rem) |
|||
end if |
|||
end procedure |
|||
procedure mktrees(integer n) |
|||
if offset[n+2]=0 then |
|||
if n>0 then |
|||
mktrees(n - 1) |
|||
end if |
|||
assemble(0, n, n-1, offset[n], n-1) |
|||
offset[n+2] = length(list) |
|||
end if |
|||
end procedure |
|||
procedure main(integer n) |
|||
mktrees(n) |
|||
atom nt = offset[n+2]-offset[n+1], |
|||
td = time()-t0 |
|||
string e = iff(td>0.1?" ("&elapsed(td)&")":"") |
|||
printf(1,"Number of %d-trees: %,d%s\n", {n, nt, e}) |
|||
if n<=5 then listTrees(n) end if |
|||
end procedure |
|||
for i=0 to 20 do |
|||
main(i) |
|||
end for</lang> |
|||
{{out}} |
|||
<pre> |
|||
Number of 0-trees: 0 |
|||
Number of 1-trees: 1 |
|||
() |
|||
Number of 2-trees: 1 |
|||
({}) |
|||
Number of 3-trees: 2 |
|||
({[]}) |
|||
({}{}) |
|||
Number of 4-trees: 4 |
|||
({[()]}) |
|||
({[][]}) |
|||
({[]}{}) |
|||
({}{}{}) |
|||
Number of 5-trees: 9 |
|||
({[({})]}) |
|||
({[()()]}) |
|||
({[()][]}) |
|||
({[][][]}) |
|||
({[()]}{}) |
|||
({[][]}{}) |
|||
({[]}{[]}) |
|||
({[]}{}{}) |
|||
({}{}{}{}) |
|||
Number of 6-trees: 20 |
|||
Number of 7-trees: 48 |
|||
Number of 8-trees: 115 |
|||
Number of 9-trees: 286 |
|||
Number of 10-trees: 719 |
|||
Number of 11-trees: 1,842 |
|||
Number of 12-trees: 4,766 |
|||
Number of 13-trees: 12,486 |
|||
Number of 14-trees: 32,973 |
|||
Number of 15-trees: 87,811 |
|||
Number of 16-trees: 235,381 (0.2s) |
|||
Number of 17-trees: 634,847 (0.5s) |
|||
Number of 18-trees: 1,721,159 (1.3s) |
|||
Number of 19-trees: 4,688,676 (4.0s) |
|||
Number of 20-trees: 12,826,228 (13.6s) |
|||
</pre> |
|||
Beyond that it gets extremely slow. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||