List rooted trees: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→{{header|jq}}: subsecond times) |
m (→{{header|Wren}}: Minor tidy) |
||
(2 intermediate revisions by one other user not shown) | |||
Line 37:
{{trans|Python}}
<
I n == 0
R [x]
Line 72:
L(x) bags(5)
print(replace_brackets(x[1]))</
{{out}}
Line 89:
=={{header|C}}==
Trees are represented by integers. When written out in binary with LSB first, 1 is opening bracket and 0 is closing.
<
#include <stdlib.h>
Line 172:
return 0;
}</
{{out}}
<pre>
Line 190:
=={{header|C++}}==
{{trans|Java}}
<
#include <vector>
Line 280:
return 0;
}</
{{out}}
<pre>Number of 5-trees: 9
Line 295:
=={{header|D}}==
{{trans|C}}
<
alias Tree = ulong,
Line 380:
stderr.writefln("Number of %d-trees: %u", n, offset[n + 1] - offset[n]);
listTees(n, offset, list);
}</
{{out}}
<pre>Number of 5-trees: 9
Line 395:
=={{header|Go}}==
{{trans|C}}
<
import (
Line 494:
fmt.Fprintf(os.Stderr, "Number of %d-trees: %d\n", n, offset[n+1]-offset[n])
listTrees(uint(n))
}</
{{out}}
Line 513:
=={{header|Haskell}}==
There probably is a nicer way than the following--
<
parts :: Int -> [[(Int, Int)]]
parts n = f n 1
Line 546:
main :: IO ()
main = mapM_ putStrLn $ trees 5</
{{out}}
<pre>
Line 562:
A variant expressed in terms of Data.Tree
<
import Data.Ord (comparing)
import Data.Tree (Tree (..), foldTree)
Line 608:
forest
| root == x = nest <> [Node i []]
| otherwise = (`go` (i, x)) <$> nest</
{{Out}}
<pre>(()()()())
Line 624:
Support code:
<
incr=: ,/@(,"1 0/ i.@{:@$)
boxed=: $:&0 :(<@\:~@([ $:^:(0 < #@]) I.@:=))"1 1 0</
Task:
Line 654:
So, for example, here is what some intermediate results would look like for the four bag case:
<
_ 0 0 0
_ 0 0 1
Line 660:
_ 0 1 0
_ 0 1 1
_ 0 1 2</
Each row represents a bag with another three bags stuffed into it. Each column represents a bag, and each index is the column of the bag that it is stuffed into. (The first bag isn't stuffed into another bag.)
Line 666:
But some of these are equivalent, we can see that if we use our parenthesis notation and think about how they could be rearranged:
<
disp incr^:3 root
(()()())
Line 673:
((())())
((()()))
(((())))</
But that's not a convenient way of finding the all of the duplicates. So we use a boxed representation - with all boxes at each level in a canonical order (fullest first) - and that makes the duplicates obvious:
Line 690:
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.List;
Line 780:
test(5);
}
}</
{{out}}
<pre>Number of 5-trees: 9
Line 796:
===ES6===
Composing a solution from generic functions.
<
'use strict';
Line 1,017:
// MAIN ---
return main()
})();</
{{Out}}
<pre>(()()()())
Line 1,044:
(*) Subsecond times in the case of the C implementation of jq.
<
def addbag:
def sortmap: map(sortmap) | sort;
Line 1,075:
"",
count_rootedtrees(17)
</syntaxhighlight>
{{out}}
<pre>
Line 1,109:
=={{header|Julia}}==
{{trans|Python}}
<
[(c + 1, "(" * s * ")") for (c, s) in bagchain((0, ""), n - 1,
n < 2 ? [] : reduce(append!, [bags(x) for x in n-1:-1:1]))]
Line 1,120:
println(bag[2])
end
</
<pre>
((((()))))
Line 1,135:
=={{header|Kotlin}}==
{{trans|C}}
<
typealias Tree = Long
Line 1,216:
println("Number of $n-trees: ${offset[n + 1] - offset[n]}")
listTrees(n)
}</
{{out}}
Line 1,234:
=={{header|Lua}}==
{{trans|Java}}
<
offset = {}
Line 1,317:
init()
test(5)</
{{out}}
<pre>Number of 5-trees: 9
Line 1,332:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
The following defines functions which create a nest of functions, bags wrapped inside a main bag which are stored inside a "cabinet".
<
DeleteDuplicates[
Map[LexicographicSort,
Line 1,340:
Addbag[config_, pos_] :=
ReplacePart[config, pos -> Append[Extract[config, pos], bag[]]]
With[{n = 5}, Nest[Addbags, {cabinet[bag[]]}, n - 1] // Column]</
The output can be viewed as a tree graph by replacing the last line with <
{{out}}
Line 1,356:
=={{header|Nim}}==
{{trans|Kotlin}}
<
type
Line 1,443:
trees.make(n)
echo &"Number of {n}-trees: {trees.offsets[n + 1] - trees.offsets[n]}"
trees.print(n)</
{{out}}
Line 1,460:
=={{header|Perl}}==
{{trans|Sidef}}
<
use warnings;
use feature 'say';
Line 1,500:
}
say replace_brackets $$_[1] for bags(5);</
{{out}}
<pre>([{([])}])
Line 1,514:
=={{header|Phix}}==
{{trans|Go}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 1,589:
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 1,634:
=={{header|Python}}==
<
if not n: return [(0, "")]
Line 1,661:
return "".join(out)
for x in bags(5): print(replace_brackets(x[1]))</
{{out}}
<pre>
Line 1,676:
Another method by incrementing subtrees:
<
'''
Line 1,725:
def tostr(x): return "(" + "".join(map(tostr, x)) + ")"
for x in trees(5): print(tostr(x))</
=={{header|Racket}}==
<
(require racket/splicing data/order)
Line 1,773:
(for-each displayln (LRTs 5))
(equal? (map (compose length LRTs) (range 1 (add1 13)))
'(1 1 2 4 9 20 48 115 286 719 1842 4766 12486))) ;; https://oeis.org/A000081</
{{out}}
Line 1,791:
Bags are represented by Raku type [http://doc.raku.org/type/Bag <code>Bag</code>].
<syntaxhighlight lang="raku"
multi expand-tree ( Bag $tree ) {
Line 1,811:
.say
};
</syntaxhighlight>
{{out}}
<pre>
Line 1,828:
=={{header|REXX}}==
This REXX version uses (internally) a binary string to represent nodes on a tree (<big>'''0'''</big> is a left parenthesis, <big>'''1'''</big> is a right parenthesis). A <big>'''()'''</big> is translated to a <big>'''O'''</big>.
<
parse arg N . /*obtain optional argument from the CL.*/
if N=='' | N=="," then N=5 /*Not specified? Then use the default.*/
Line 1,856:
end /*j*/
say /*separate number─of─ways with a blank.*/
say # ' is the number of ways to nest' n "bags." /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default input:}}
<pre>
Line 1,873:
=={{header|Ring}}==
<
# Project : List rooted trees
Line 1,944:
ok
end
</syntaxhighlight>
Output:
<pre>
Line 1,963:
=={{header|Ruby}}==
{{trans|Java}}
<
OFFSET = []
Line 2,041:
end
test(5)</
{{out}}
<pre>Number of 5-trees: 9
Line 2,056:
=={{header|Sidef}}==
{{trans|Python}}
<
n || return [x]
Line 2,094:
for x in (bags(5)) {
say replace_brackets(x[1])
}</
{{out}}
<pre>
Line 2,111:
{{trans|Kotlin}}
{{libheader|Wren-long}}
<
import "os" for Process
Line 2,181:
makeTrees.call(n)
System.print("Number of %(n)-trees: %(offset[n + 1] - offset[n])")
listTrees.call(n)</
{{out}}
Line 2,200:
Note that "( () (()) () )" the same as "( (()) () () )"
{{trans|Python}}
<
if(not n) return(T(T(0,"")));
Line 2,232:
foreach x in (bags(5)){ println(replace_brackets(x[1])) }
println("or");
b:=bags(5); b.apply("get",1).println(b.len());</
{{out}}
<pre>
|