List rooted trees: Difference between revisions

m
m (→‎{{header|REXX}}: added/changed comments.)
m (→‎{{header|Wren}}: Minor tidy)
 
(17 intermediate revisions by 10 users not shown)
Line 33:
As an example output, run 5 bags.   There should be 9 ways.
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F bagchain(x, n, bb, start = 0)
I n == 0
R [x]
 
[(Int, String)] out
L(i) start .< bb.len
V (c, s) = bb[i]
I c <= n
out.extend(bagchain((x[0] + c, x[1]‘’s), n - c, bb, i))
 
R out
 
F bags(n)
I n == 0
R [(0, ‘’)]
 
[(Int, String)] upto
L(x) (n - 1 .< 0).step(-1)
upto.extend(bags(x))
 
R bagchain((0, ‘’), n - 1, upto).map((c, s) -> (c + 1, ‘(’s‘)’))
 
F replace_brackets(s)
V depth = 0
[String] out
L(c) s
I c == ‘(’
out.append(‘([{’[depth % 3])
depth++
E
depth--
out.append(‘)]}’[depth % 3])
R out.join(‘’)
 
L(x) bags(5)
print(replace_brackets(x[1]))</syntaxhighlight>
 
{{out}}
<pre>
([{([])}])
([{()()}])
([{()}{}])
([{}{}{}])
([{()}][])
([{}{}][])
([{}][{}])
([{}][][])
([][][][])
</pre>
 
=={{header|C}}==
Trees are represented by integers. When written out in binary with LSB first, 1 is opening bracket and 0 is closing.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 119 ⟶ 172:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 134 ⟶ 187:
(()()()())
</pre>
 
=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <vector>
 
std::vector<long> TREE_LIST;
std::vector<int> OFFSET;
 
void init() {
for (size_t i = 0; i < 32; i++) {
if (i == 1) {
OFFSET.push_back(1);
} else {
OFFSET.push_back(0);
}
}
}
 
void append(long t) {
TREE_LIST.push_back(1 | (t << 1));
}
 
void show(long t, int l) {
while (l-- > 0) {
if (t % 2 == 1) {
std::cout << '(';
} else {
std::cout << ')';
}
t = t >> 1;
}
}
 
void listTrees(int n) {
for (int i = OFFSET[n]; i < OFFSET[n + 1]; i++) {
show(TREE_LIST[i], 2 * n);
std::cout << '\n';
}
}
 
void assemble(int n, long t, int sl, int pos, int rem) {
if (rem == 0) {
append(t);
return;
}
 
auto pp = pos;
auto ss = sl;
 
if (sl > rem) {
ss = rem;
pp = OFFSET[ss];
} else if (pp >= OFFSET[ss + 1]) {
ss--;
if (ss == 0) {
return;
}
pp = OFFSET[ss];
}
 
assemble(n, t << (2 * ss) | TREE_LIST[pp], ss, pp, rem - ss);
assemble(n, t, ss, pp + 1, rem);
}
 
void makeTrees(int n) {
if (OFFSET[n + 1] != 0) {
return;
}
if (n > 0) {
makeTrees(n - 1);
}
assemble(n, 0, n - 1, OFFSET[n - 1], n - 1);
OFFSET[n + 1] = TREE_LIST.size();
}
 
void test(int n) {
if (n < 1 || n > 12) {
throw std::runtime_error("Argument must be between 1 and 12");
}
 
append(0);
 
makeTrees(n);
std::cout << "Number of " << n << "-trees: " << OFFSET[n + 1] - OFFSET[n] << '\n';
listTrees(n);
}
 
int main() {
init();
test(5);
 
return 0;
}</syntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
 
=={{header|D}}==
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio, std.conv;
 
alias Tree = ulong,
Line 222 ⟶ 380:
stderr.writefln("Number of %d-trees: %u", n, offset[n + 1] - offset[n]);
listTees(n, offset, list);
}</langsyntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
Line 237 ⟶ 395:
=={{header|Go}}==
{{trans|C}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 336 ⟶ 494:
fmt.Fprintf(os.Stderr, "Number of %d-trees: %d\n", n, offset[n+1]-offset[n])
listTrees(uint(n))
}</langsyntaxhighlight>
 
{{out}}
Line 355 ⟶ 513:
=={{header|Haskell}}==
There probably is a nicer way than the following--
<langsyntaxhighlight lang="haskell">-- break n down into sum of smaller integers
parts :: Int -> [[(Int, Int)]]
parts n = f n 1
Line 388 ⟶ 546:
 
main :: IO ()
main = mapM_ putStrLn $ trees 5</langsyntaxhighlight>
{{out}}
<pre>
Line 404 ⟶ 562:
A variant expressed in terms of Data.Tree
 
<langsyntaxhighlight lang="haskell">import Data.List (nubfoldl', sortBynub, foldl'sortOn) --' strict variant of foldl
import Data.Tree (Tree(..), foldTree)
import Data.Ord (comparing)
import Data.Tree (Tree (..), foldTree)
 
-------------------- LIST ROOTED TREES -------------------
 
bagPatterns :: Int -> [String]
bagPatterns n =
nub $
foldTree asBrackets
bracketsFromTree . depthSortedTree . treeFromParentIndices <$>
. foldTree depthSorted
parentIndexPermutations n
. treeFromParentIndices
<$> parentIndexPermutations n
 
--------------------------- TEST--- -------------------------
main :: IO ()
main = putStrLn . unlines $ bagPatterns 5
 
------------------------ DEFINITIONS-- ----------------------
depthSortedTree
:: (Enum a, Num a, Ord a)
=> Tree a -> Tree a
depthSortedTree tree
| null (subForest tree) = Node 0 []
| otherwise =
let xs = depthSortedTree <$> subForest tree
in Node
(succ $ foldr ((+) . rootLabel) 0 xs)
(sortBy (flip (comparing rootLabel)) xs)
 
bracketsFromTreeasBrackets :: Tree a -> [String] -> String
bracketsFromTreeasBrackets = foldTreeconst (\_ xs -> ('(' :) . (concat xs ++<> ")") . concat)
 
depthSorted :: a -> [Tree Int] -> Tree Int
depthSorted = const (Node <$> length <*> sortOn rootLabel)
 
parentIndexPermutations :: Int -> [[Int]]
parentIndexPermutations = traverse (enumFromTo 0) . enumFromTo 0 . subtract 2
traverse
(enumFromTo 0)
. enumFromTo 0
. subtract 2
 
treeFromParentIndices :: [Int] -> Tree Int
Line 448 ⟶ 607:
nest = subForest tree
forest
| root == x = nest ++<> [Node i []]
| otherwise = (`go` (i, x)) <$> nest</langsyntaxhighlight>
{{Out}}
<pre>(()()()())
((())()(()))
((()()()()))
((())(()))
(()((()))())
((()()()))
(((())(())))
(((()())))
((((()))))</pre>
Line 465 ⟶ 624:
Support code:
 
<langsyntaxhighlight Jlang="j">root=: 1 1 $ _
incr=: ,/@(,"1 0/ i.@{:@$)
 
boxed=: $:&0 :(<@\:~@([ $:^:(0 < #@]) I.@:=))"1 1 0</langsyntaxhighlight>
 
Task:
Line 495 ⟶ 654:
So, for example, here is what some intermediate results would look like for the four bag case:
 
<langsyntaxhighlight Jlang="j"> incr^:3 root
_ 0 0 0
_ 0 0 1
Line 501 ⟶ 660:
_ 0 1 0
_ 0 1 1
_ 0 1 2</langsyntaxhighlight>
 
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 507 ⟶ 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:
 
<langsyntaxhighlight Jlang="j"> disp=: ('(' , ')' ,~ [: ; [ <@disp"1 0^:(0 < #@]) I.@:=) {.
disp incr^:3 root
(()()())
Line 514 ⟶ 673:
((())())
((()()))
(((())))</langsyntaxhighlight>
 
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 531 ⟶ 690:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
 
Line 621 ⟶ 780:
test(5);
}
}</langsyntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
Line 637 ⟶ 796:
===ES6===
Composing a solution from generic functions.
<langsyntaxhighlight lang="javascript">(() => {
'use strict';
 
Line 858 ⟶ 1,017:
// MAIN ---
return main()
})();</langsyntaxhighlight>
{{Out}}
<pre>(()()()())
Line 869 ⟶ 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.
 
<syntaxhighlight lang="jq"># add one bag somewhere
def addbag:
def sortmap: map(sortmap) | sort;
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)
</syntaxhighlight>
{{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}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">bags(n,cache="") = n < 1 ? [(0, "")] :
[(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 883 ⟶ 1,120:
println(bag[2])
end
</langsyntaxhighlight>{{out}}
<pre>
((((()))))
Line 898 ⟶ 1,135:
=={{header|Kotlin}}==
{{trans|C}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
typealias Tree = Long
Line 979 ⟶ 1,216:
println("Number of $n-trees: ${offset[n + 1] - offset[n]}")
listTrees(n)
}</langsyntaxhighlight>
 
{{out}}
Line 994 ⟶ 1,231:
(()()()())
</pre>
 
=={{header|Lua}}==
{{trans|Java}}
<syntaxhighlight lang="lua">tree_list = {}
offset = {}
 
function init()
for i=1,32 do
if i == 2 then
table.insert(offset, 1)
else
table.insert(offset, 0)
end
end
end
 
function append(t)
local v = 1 | (t << 1)
table.insert(tree_list, v)
end
 
function show(t, l)
while l > 0 do
l = l - 1
if (t % 2) == 1 then
io.write('(')
else
io.write(')')
end
t = t >> 1
end
end
 
function listTrees(n)
local i = offset[n]
while i < offset[n + 1] do
show(tree_list[i + 1], n * 2)
print()
i = i + 1
end
end
 
function assemble(m, t, sl, pos, rem)
if rem == 0 then
append(t)
return
end
 
local pp = pos
local ss = sl
 
if sl > rem then
ss = rem
pp = offset[ss]
elseif pp >= offset[ss + 1] then
ss = ss - 1
if ss == 0 then
return
end
pp = offset[ss]
end
 
assemble(n, t << (2 * ss) | tree_list[pp + 1], ss, pp, rem - ss)
assemble(n, t, ss, pp + 1, rem)
end
 
function makeTrees(n)
if offset[n + 1] ~= 0 then
return
end
if n > 0 then
makeTrees(n - 1)
end
assemble(n, 0, n - 1, offset[n - 1], n - 1)
offset[n + 1] = #tree_list
end
 
function test(n)
append(0)
 
makeTrees(n)
print(string.format("Number of %d-trees: %d", n, offset[n+1] - offset[n]))
listTrees(n)
end
 
init()
test(5)</syntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
 
=={{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".
<syntaxhighlight lang="mathematica">Addbags[configs_List] :=
DeleteDuplicates[
Map[LexicographicSort,
Catenate[AddbagAll /@ configs], \[Infinity]]]
AddbagAll[config_] :=
Addbag[config, #] & /@ Position[config, bag[___], \[Infinity]]
Addbag[config_, pos_] :=
ReplacePart[config, pos -> Append[Extract[config, pos], bag[]]]
With[{n = 5}, Nest[Addbags, {cabinet[bag[]]}, n - 1] // Column]</syntaxhighlight>
The output can be viewed as a tree graph by replacing the last line with <syntaxhighlight lang="mathematica">With[{n = 5}, TreeForm /@ Nest[Addbags, {cabinet[bag[]]}, n - 1]]</syntaxhighlight>
 
{{out}}
<pre>cabinet[bag[bag[bag[bag[bag[]]]]]]
cabinet[bag[bag[bag[bag[],bag[]]]]]
cabinet[bag[bag[bag[],bag[bag[]]]]]
cabinet[bag[bag[],bag[bag[bag[]]]]]
cabinet[bag[bag[bag[],bag[],bag[]]]]
cabinet[bag[bag[],bag[bag[],bag[]]]]
cabinet[bag[bag[bag[]],bag[bag[]]]]
cabinet[bag[bag[],bag[],bag[bag[]]]]
cabinet[bag[bag[],bag[],bag[],bag[]]]</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import os, strformat, strutils
 
type
Tree = int
Trees = object
list: seq[Tree]
offsets: array[32, int]
 
 
func isOdd(n: int): bool = (n and 1) != 0
 
 
func append(trees: var Trees; tree: Tree) =
trees.list.add(1 or tree shl 1)
 
 
proc show(tree: Tree; n: int) =
var tree = tree
var n = n
while n > 0:
dec n
stdout.write if tree.isOdd: '(' else: ')'
tree = tree shr 1
stdout.write '\n'
 
 
proc print(trees: Trees; n: int) =
for i in trees.offsets[n]..<trees.offsets[n + 1]:
trees.list[i].show(n * 2)
 
 
#[ Assemble tree from subtrees
n: length of tree we want to make
t: assembled parts so far
sl: length of subtree we are looking at
pos: offset of subtree we are looking at
rem: remaining length to be put together
]#
 
func assemble(trees: var Trees; n: int; t: Tree; sl, pos, rem: int) =
 
if rem == 0:
trees.append(t)
return
 
var p = pos
var s = sl
 
if s > rem:
s = rem
p = trees.offsets[s]
elif p >= trees.offsets[s + 1]:
# Used up sl-trees, try smaller ones.
dec s
if s == 0: return
p = trees.offsets[s]
 
trees.assemble(n, t shl ( 2 * s) or trees.list[p], s, p, rem - s)
trees.assemble(n, t, s, p + 1, rem)
 
 
func make(trees: var Trees; n: int) =
if trees.offsets[n + 1] != 0: return
if n > 0: trees.make(n - 1)
trees.assemble(n, 0, n - 1, trees.offsets[n - 1], n - 1)
trees.offsets[n + 1] = trees.list.len
 
 
when isMainModule:
 
if paramCount() != 1:
raise newException(ValueError, "there must be exactly one command line argument")
let n = try:
paramStr(1).parseInt()
except ValueError:
raise newException(ValueError, "argument is not a valid number")
# Insure "n" is limited to 12 to avoid overflowing default stack.
if n notin 1..12:
raise newException(ValueError, "argument must be between 1 and 12")
 
# Init 1-tree.
var trees: Trees
trees.offsets[1] = 1
trees.append(0)
 
trees.make(n)
echo &"Number of {n}-trees: {trees.offsets[n + 1] - trees.offsets[n]}"
trees.print(n)</syntaxhighlight>
 
{{out}}
For instance, for n = 5:
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
 
=={{header|Perl}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 1,037 ⟶ 1,500:
}
 
say replace_brackets $$_[1] for bags(5);</langsyntaxhighlight>
{{out}}
<pre>([{([])}])
Line 1,051 ⟶ 1,514:
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>atom t0 = time()
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence list = {1},
<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>
offset = repeat(0,32)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
offset[1..2] = 1
<span style="color: #000000;">offset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
function show(integer t, l)
string res = repeat('?',l)
<span style="color: #008080;">function</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
integer level = 0
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'?'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
for i=l to 1 by -1 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">level</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer r2 = remainder(t,2)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
res[i] = "[}(]{)"[mod(level-r2,6)+1]
<span style="color: #004080;">integer</span> <span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
level += r2*4-2
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"[}(]{)"</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">level</span><span style="color: #0000FF;">-</span><span style="color: #000000;">r2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
t = floor(t/2)
<span style="color: #000000;">level</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">r2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span>
end for
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
if level!=0 then ?9/0 end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure listTrees(integer n)
for i:=offset[n+1]+1 to offset[n+2] do
<span style="color: #008080;">procedure</span> <span style="color: #000000;">listTrees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
printf(1,"%s\n",{show(list[i], n*2)})
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">:=</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
end for
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure assemble(atom t, integer n, sl, pos, rem)
--
<span style="color: #008080;">procedure</span> <span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span>
-- assemble tree from subtrees
<span style="color: #000080;font-style:italic;">--
-- t: assembled parts so far
-- n: length ofassemble tree we want tofrom makesubtrees
-- slt: length ofassembled subtreeparts weso are looking atfar
-- posn: offset length of subtreetree we arewant lookingto atmake
-- remsl: remaining length toof besubtree putwe togetherare looking at
-- pos: offset of subtree we are looking at
--
-- rem: remaining length to be put together
if rem == 0 then
--</span>
list = append(list, t*2+1)
<span style="color: #008080;">if</span> <span style="color: #000000;">rem</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
if sl>rem then -- need smaller sub-trees
<span style="color: #008080;">else</span>
sl = rem
<span style="color: #008080;">if</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">></span><span style="color: #000000;">rem</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- need smaller sub-trees</span>
pos = offset[sl+1]
<span style="color: #000000;">sl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rem</span>
elsif pos>=offset[sl+2] then
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
-- used up sl-trees, try smaller ones
<span style="color: #008080;">elsif</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
if sl == 1 then return end if
<span style="color: #000080;font-style:italic;">-- used up sl-trees, try smaller ones</span>
pos = offset[sl]
<span style="color: #008080;">if</span> <span style="color: #000000;">sl</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sl -= 1
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">sl</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
atom u = or_bits(t*power(2,2*sl),list[pos+1])
assemble(u, n, sl, pos, rem-sl)
<span style="color: #004080;">atom</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">or_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">),</span><span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
assemble(t, n, sl, pos+1, rem)
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">-</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure mktrees(integer n)
if offset[n+2]=0 then
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if n>0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
mktrees(n - 1)
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
assemble(0, n, n-1, offset[n], n-1)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
offset[n+2] = length(list)
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure main(integer n)
mktrees(n)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
atom nt = offset[n+2]-offset[n+1],
<span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
td = time()-t0
<span style="color: #004080;">atom</span> <span style="color: #000000;">nt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
string e = iff(td>0.1?" ("&elapsed(td)&")":"")
<span style="color: #000000;">td</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
printf(1,"Number of %d-trees: %,d%s\n", {n, nt, e})
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">td</span><span style="color: #0000FF;">></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" ("</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">td</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
if n<=5 then listTrees(n) end if
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Number of %d-trees: %,d%s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">listTrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=0 to 20 do
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
main(i)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">12</span><span style="color: #0000FF;">:</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for</lang>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,165 ⟶ 1,631:
Number of 20-trees: 12,826,228 (13.6s)
</pre>
Beyond that it gets extremely slow. Under pwa/p2js 14-trees exceeded the JavaScript call stack limit, so I knocked a couple more off for safety.
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def bags(n,cache={}):
if not n: return [(0, "")]
 
Line 1,195 ⟶ 1,661:
return "".join(out)
 
for x in bags(5): print(replace_brackets(x[1]))</langsyntaxhighlight>
{{out}}
<pre>
Line 1,210 ⟶ 1,676:
 
Another method by incrementing subtrees:
<langsyntaxhighlight lang="python">treeid = {(): 0}
 
'''
Line 1,259 ⟶ 1,725:
def tostr(x): return "(" + "".join(map(tostr, x)) + ")"
 
for x in trees(5): print(tostr(x))</langsyntaxhighlight>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(require racket/splicing data/order)
 
Line 1,307 ⟶ 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</langsyntaxhighlight>
 
{{out}}
Line 1,325 ⟶ 1,791:
Bags are represented by Raku type [http://doc.raku.org/type/Bag <code>Bag</code>].
 
<syntaxhighlight lang="raku" perl6line>use v6;
 
multi expand-tree ( Bag $tree ) {
Line 1,345 ⟶ 1,811:
.say
};
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,362 ⟶ 1,828:
=={{header|REXX}}==
This REXX version uses (internally) a binary string to represent nodes on a tree &nbsp; (<big>'''0'''</big> &nbsp; is a left parenthesis, &nbsp; <big>'''1'''</big> &nbsp; is a right parenthesis). &nbsp; A &nbsp; <big>'''()'''</big> &nbsp; is translated to a &nbsp; <big>'''O'''</big>.
<langsyntaxhighlight lang="rexx">/*REXX program lists n─node rooted trees (by enumerating all ways of nesting N bags).*/
parse arg N . /*obtain optional argument from the CL.*/
if N=='' | N=="," then N=5 /*Not specified? Then use the default.*/
Line 1,390 ⟶ 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. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 1,407 ⟶ 1,873:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : List rooted trees
 
Line 1,478 ⟶ 1,944:
ok
end
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,494 ⟶ 1,960:
(((())))
</pre>
 
=={{header|Ruby}}==
{{trans|Java}}
<syntaxhighlight lang="ruby">TREE_LIST = []
OFFSET = []
 
for i in 0..31
if i == 1 then
OFFSET << 1
else
OFFSET << 0
end
end
 
def append(t)
TREE_LIST << (1 | (t << 1))
end
 
def show(t, l)
while l > 0
l = l - 1
if t % 2 == 1 then
print '('
else
print ')'
end
t = t >> 1
end
end
 
def listTrees(n)
for i in OFFSET[n] .. OFFSET[n + 1] - 1
show(TREE_LIST[i], n * 2)
print "\n"
end
end
 
def assemble(n, t, sl, pos, rem)
if rem == 0 then
append(t)
return
end
 
if sl > rem then
sl = rem
pos = OFFSET[sl]
elsif pos >= OFFSET[sl + 1] then
sl = sl - 1
if sl == 0 then
return
end
pos = OFFSET[sl]
end
 
assemble(n, t << (2 * sl) | TREE_LIST[pos], sl, pos, rem - sl)
assemble(n, t, sl, pos + 1, rem)
end
 
def makeTrees(n)
if OFFSET[n + 1] != 0 then
return
end
if n > 0 then
makeTrees(n - 1)
end
assemble(n, 0, n - 1, OFFSET[n - 1], n - 1)
OFFSET[n + 1] = TREE_LIST.length()
end
 
def test(n)
if n < 1 || n > 12 then
raise ArgumentError.new("Argument must be between 1 and 12")
end
 
append(0)
 
makeTrees(n)
print "Number of %d-trees: %d\n" % [n, OFFSET[n + 1] - OFFSET[n]]
listTrees(n)
end
 
test(5)</syntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
 
=={{header|Sidef}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">func bagchain(x, n, bb, start=0) {
n || return [x]
 
Line 1,535 ⟶ 2,094:
for x in (bags(5)) {
say replace_brackets(x[1])
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,547 ⟶ 2,106:
([{}][][])
([][][][])
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-long}}
<syntaxhighlight lang="wren">import "./long" for ULong
import "os" for Process
 
var treeList = []
var offset = List.filled(32, 0)
offset[1] = 1
 
var append = Fn.new { |t|
treeList.add(ULong.one | (t << 1))
}
 
var show = Fn.new { |t, len|
while (len > 0) {
len = len - 1
System.write(t.isOdd ? "(" : ")")
t = t >> 1
}
}
 
var listTrees = Fn.new { |n|
for (i in offset[n]...offset[n+1]) {
show.call(treeList[i], n * 2)
System.print()
}
}
 
/* assemble tree from subtrees
n: length of tree we want to make
t: assembled parts so far
sl: length of subtree we are looking at
pos: offset of subtree we are looking at
rem: remaining length to be put together
*/
 
var assemble // recursive
assemble = Fn.new { |n, t, sl, pos, rem|
if (rem == 0) {
append.call(t)
return
}
if (sl > rem) { // need smaller subtrees
pos = offset[sl = rem]
} else if (pos >= offset[sl + 1]) {
// used up sl-trees, try smaller ones
sl = sl - 1
if (sl == 0) return
pos = offset[sl]
}
assemble.call(n, (t << (2 * sl)) | treeList[pos], sl, pos, rem - sl)
assemble.call(n, t, sl, pos + 1, rem)
}
 
var makeTrees // recursive
makeTrees = Fn.new { |n|
if (offset[n + 1] != 0) return
if (n > 0) makeTrees.call(n - 1)
assemble.call(n, ULong.zero, n - 1, offset[n - 1], n - 1)
offset[n + 1] = treeList.count
}
 
var args = Process.arguments
if (args.count != 1) Fiber.abort("There must be exactly 1 command line argument.")
var n = Num.fromString(args[0])
if (!n) Fiber.abort("Argument is not a valid number.")
if (n < 1 || n > 12) Fiber.abort("Argument must be between 1 and 12.")
 
// init 1-tree
append.call(ULong.zero)
makeTrees.call(n)
System.print("Number of %(n)-trees: %(offset[n + 1] - offset[n])")
listTrees.call(n)</syntaxhighlight>
 
{{out}}
<pre>
Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())
</pre>
 
Line 1,552 ⟶ 2,200:
Note that "( () (()) () )" the same as "( (()) () () )"
{{trans|Python}}
<langsyntaxhighlight lang="zkl">fcn bags(n){
if(not n) return(T(T(0,"")));
 
Line 1,584 ⟶ 2,232:
foreach x in (bags(5)){ println(replace_brackets(x[1])) }
println("or");
b:=bags(5); b.apply("get",1).println(b.len());</langsyntaxhighlight>
{{out}}
<pre>
9,486

edits