List rooted trees: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Haskell}}: Tidying) |
m (→{{header|Wren}}: Minor tidy) |
||
(25 intermediate revisions by 12 users not shown) | |||
Line 1:
{{
You came back from grocery shopping. After putting away all the goods, you are left with a pile of plastic bags, which you want to save for later use, so you take one bag and stuff all the others into it, and throw it under the sink. In doing so, you realize that there are various ways of nesting the bags, with all bags viewed as identical.
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.
<
#include <stdlib.h>
Line 119 ⟶ 172:
return 0;
}</
{{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}}
<
alias Tree = ulong,
Line 222 ⟶ 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 237 ⟶ 395:
=={{header|Go}}==
{{trans|C}}
<
import (
Line 336 ⟶ 494:
fmt.Fprintf(os.Stderr, "Number of %d-trees: %d\n", n, offset[n+1]-offset[n])
listTrees(uint(n))
}</
{{out}}
Line 355 ⟶ 513:
=={{header|Haskell}}==
There probably is a nicer way than the following--
<
parts
where
f n x
| n == 0 = [[]]
| x > n = []
| otherwise =
f n (x + 1) ++
concatMap
(\c -> map ((c, x) :) (f (n - c * x) (x + 1)))
[1 .. n `div` x]
-- choose n strings out of a list and join them
pick :: Int -> [String] -> [String]
pick _ [] = []
pick 0 _ = [""]
pick n aa@(a:as) = map (a ++) (pick (n - 1) aa) ++ pick n as
-- pick parts to build a series of subtrees that add up to n-1,
-- then wrap them up
trees :: Int -> [String]
trees n =
map (\x -> "(" ++ x ++ ")") $
concatMap (foldr (prod . build) [""]) (parts (n - 1))
where
build (c, x) = pick c $ trees x
prod aa bb =
[ a ++ b
| a <- aa
, b <- bb ]
main :: IO ()
main = mapM_ putStrLn $ trees 5</syntaxhighlight>
{{out}}
<pre>
Line 385 ⟶ 560:
</pre>
A variant
<
import Data.Ord (comparing)
import Data.Tree (Tree (..), foldTree)
-------------------- LIST ROOTED TREES -------------------
bagPatterns :: Int -> [String]
bagPatterns n =
nub $
foldTree asBrackets
. foldTree depthSorted
. treeFromParentIndices
<$> parentIndexPermutations n
--------------------------- TEST -------------------------
main :: IO ()
main = putStrLn . unlines $ bagPatterns 5
----------------------- DEFINITIONS ----------------------
asBrackets :: a -> [String] -> String
asBrackets = const (('(' :) . (<> ")") . concat)
depthSorted :: a -> [Tree Int] -> Tree Int
depthSorted = const (Node <$> length <*> sortOn rootLabel)
parentIndexPermutations :: Int -> [[Int]]
parentIndexPermutations =
traverse
(enumFromTo 0)
. enumFromTo 0
. subtract 2
treeFromParentIndices :: [Int] -> Tree Int
treeFromParentIndices
foldl' --' strict variant of foldl
go
(Node 0 [])
(zip [1 ..
where
go tree
where
nest =
forest
| otherwise = (`go` (i, x)) <$> nest</syntaxhighlight>
{{Out}}
<pre>(()()()())
((())(()))
(()((())
((()()()))
(((()())))
((((()))))</pre>
Line 453 ⟶ 624:
Support code:
<
incr=: ,/@(,"1 0/ i.@{:@$)
boxed=: $:&0 :(<@\:~@([ $:^:(0 < #@]) I.@:=))"1 1 0</
Task:
Line 483 ⟶ 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 489 ⟶ 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 495 ⟶ 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 502 ⟶ 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 516 ⟶ 687:
│ │ │ │ │ │└────┘│
└────┴─────┴─────┴─────┴─────┴──────┘</pre>
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
public class ListRootedTrees {
private static final List<Long> TREE_LIST = new ArrayList<>();
private static final List<Integer> OFFSET = new ArrayList<>();
static {
for (int i = 0; i < 32; i++) {
if (i == 1) {
OFFSET.add(1);
} else {
OFFSET.add(0);
}
}
}
private static void append(long t) {
TREE_LIST.add(1 | (t << 1));
}
private static void show(long t, int l) {
while (l-- > 0) {
if (t % 2 == 1) {
System.out.print('(');
} else {
System.out.print(')');
}
t = t >> 1;
}
}
private static void listTrees(int n) {
for (int i = OFFSET.get(n); i < OFFSET.get(n + 1); i++) {
show(TREE_LIST.get(i), n * 2);
System.out.println();
}
}
private static void assemble(int n, long t, int sl, int pos, int rem) {
if (rem == 0) {
append(t);
return;
}
var pp = pos;
var ss = sl;
if (sl > rem) {
ss = rem;
pp = OFFSET.get(ss);
} else if (pp >= OFFSET.get(ss + 1)) {
ss--;
if (ss == 0) {
return;
}
pp = OFFSET.get(ss);
}
assemble(n, t << (2 * ss) | TREE_LIST.get(pp), ss, pp, rem - ss);
assemble(n, t, ss, pp + 1, rem);
}
private static void makeTrees(int n) {
if (OFFSET.get(n + 1) != 0) {
return;
}
if (n > 0) {
makeTrees(n - 1);
}
assemble(n, 0, n - 1, OFFSET.get(n - 1), n - 1);
OFFSET.set(n + 1, TREE_LIST.size());
}
private static void test(int n) {
if (n < 1 || n > 12) {
throw new IllegalArgumentException("Argument must be between 1 and 12");
}
append(0);
makeTrees(n);
System.out.printf("Number of %d-trees: %d\n", n, OFFSET.get(n + 1) - OFFSET.get(n));
listTrees(n);
}
public static void main(String[] args) {
test(5);
}
}</syntaxhighlight>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
=={{header|Javascript}}==
===ES6===
Composing a solution from generic functions.
<
'use strict';
Line 741 ⟶ 1,017:
// MAIN ---
return main()
})();</
{{Out}}
<pre>(()()()())
Line 752 ⟶ 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}}
<
[(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 766 ⟶ 1,120:
println(bag[2])
end
</
<pre>
((((()))))
Line 778 ⟶ 1,132:
(()()()())
</pre>
=={{header|Kotlin}}==
{{trans|C}}
<
typealias Tree = Long
Line 863 ⟶ 1,216:
println("Number of $n-trees: ${offset[n + 1] - offset[n]}")
listTrees(n)
}</
{{out}}
Line 878 ⟶ 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}}
<
use warnings;
use feature 'say';
Line 921 ⟶ 1,500:
}
say replace_brackets $$_[1] for bags(5);</
{{out}}
<pre>([{([])}])
Line 932 ⟶ 1,511:
([{}][][])
([][][][])</pre>
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<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>
<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>
<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>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">level</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<span style="color: #000080;font-style:italic;">--
--
--
--
--
-- pos: offset of subtree we are looking at
-- rem: remaining length to be put together
--</span>
<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>
<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>
<span style="color: #008080;">else</span>
<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>
<span style="color: #000000;">sl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rem</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;">1</span><span style="color: #0000FF;">]</span>
<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>
<span style="color: #000080;font-style:italic;">-- used up sl-trees, try smaller ones</span>
<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>
<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;">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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<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: #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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<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,087 ⟶ 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}}==
<
if not n: return [(0, "")]
Line 1,117 ⟶ 1,661:
return "".join(out)
for x in bags(5): print(replace_brackets(x[1]))</
{{out}}
<pre>
Line 1,132 ⟶ 1,676:
Another method by incrementing subtrees:
<
'''
Line 1,181 ⟶ 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,229 ⟶ 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,242 ⟶ 1,786:
((((()))))
#t</pre>
=={{header|Raku}}==
(formerly Perl 6)
Bags are represented by Raku type [http://doc.raku.org/type/Bag <code>Bag</code>].
<syntaxhighlight lang="raku" line>use v6;
multi expand-tree ( Bag $tree ) {
bag(bag(bag()) (+) $tree) (+)
[(+)] (
$tree.keys ==> map {
$^a.&expand-tree.map: * (+) ( $tree (-) bag($^a) )
}
);
}
multi expand-trees ( Bag $trees ) {
[(+)] $trees.keys.map: { $_.&expand-tree } ;
}
my $n = 5;
for ( bag(), bag(bag()), *.&expand-trees ... * )[$n] {
print ++$,".\t";
.say
};
</syntaxhighlight>
{{out}}
<pre>
1. bag(bag(), bag(bag()(2))) => 2
2. bag(bag(bag()(3))) => 1
3. bag(bag(bag(bag()), bag())) => 2
4. bag(bag(bag(bag(bag())))) => 1
5. bag(bag(bag())(2)) => 1
6. bag(bag(bag(bag()(2)))) => 1
7. bag(bag(), bag(bag(bag()))) => 2
8. bag(bag(bag()), bag()(2)) => 2
9. bag(bag()(4)) => 1
</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.
=={{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,254 ⟶ 1,837:
start= 2**nn + (2**nn) % 2 /*calculate the starting decimal number*/
if N==1 then start= 2**1 /*treat the start for unity as special.*/
#= 0 /*count of ways to nest bags (so far). */
$= /*string holds possible duplicious strs*/
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,290 ⟶ 1,873:
=={{header|Ring}}==
<
# Project : List rooted trees
Line 1,361 ⟶ 1,944:
ok
end
</syntaxhighlight>
Output:
<pre>
Line 1,377 ⟶ 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}}
<
n || return [x]
Line 1,418 ⟶ 2,094:
for x in (bags(5)) {
say replace_brackets(x[1])
}</
{{out}}
<pre>
Line 1,430 ⟶ 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,435 ⟶ 2,200:
Note that "( () (()) () )" the same as "( (()) () () )"
{{trans|Python}}
<
if(not n) return(T(T(0,"")));
Line 1,467 ⟶ 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>
|