List rooted trees: Difference between revisions
→{{header|jq}}
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
|||
Line 1,028:
(((()())))
((((()))))</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
In this entry, a straightforward approach is used:
bags are added one at a time, employing the one-liner `sortmap`
to select canonical representations.
`rootedtrees($n)` displays the rooted trees of order $n as a stream of JSON arrays. `count_rootedtrees($n) displays a table of [$n, $count] values, where $count is the number of $n-trees.
For trees of order up to about 12, the algorithm is quite snappy (*).
Beyond 17, the results are very slow in coming, and hence the limit in the displayed table.
(*) Subsecond times in the case of the C implementation of jq, which nicely optimizes the
recursive function `sortmap`.
<lang jq># add one bag somewhere
def addbag:
def sortmap: sort | map(sortmap);
if . == null then [] # one bag
else ([[]] + .),
(paths as $p
| getpath($p) as $x
| setpath($p; [[]] + $x)
| sortmap # indistinguishability of bags
)
end ;
# emit a stream of the distinct rooted trees of order $n > 0
def rootedtrees($n):
if $n==1 then []
else foreach range(0; $n-1) as $i ([[]];
[.[] | addbag] | unique;
select($i == $n-2))
| .[]
end;
# emit $n arrays of the form [$i, $count] for 0 < $i <= $n
def count_rootedtrees($n):
[1, 1],
foreach range(0; $n - 1) as $i ([[]];
[.[] | addbag] | unique;
[$i + 2, length]) ;
rootedtrees(5),
"",
count_rootedtrees(17)
</lang>
{{out}}
<pre>
[[],[],[],[]]
[[],[],[[]]]
[[],[[],[]]]
[[],[[[]]]]
[[[]],[[]]]
[[[],[],[]]]
[[[],[[]]]]
[[[[],[]]]]
[[[[[]]]]]
[1,1]
[2,1]
[3,2]
[4,4]
[5,9]
[6,20]
[7,48]
[8,115]
[9,286]
[10,719]
[11,1842]
[12,4766]
[13,12486]
[14,32973]
[15,87811]
[16,235381]
[17,634847]
</pre>
=={{header|Julia}}==
| |||