List rooted trees: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (added a ;Task: (bold) header.) |
m (→{{header|Wren}}: Minor tidy) |
||
| (46 intermediate revisions by 14 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 234 ⟶ 392:
(()()(()))
(()()()())</pre>
=={{header|Go}}==
{{trans|C}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"log"
"os"
"strconv"
)
type tree uint64
var (
list []tree
offset = [32]uint{1: 1}
)
func add(t tree) {
list = append(list, 1|t<<1)
}
func show(t tree, l uint) {
for ; l > 0; t >>= 1 {
l--
var paren byte
if (t & 1) != 0 {
paren = '('
} else {
paren = ')'
}
fmt.Printf("%c", paren)
}
}
func listTrees(n uint) {
for i := offset[n]; i < offset[n+1]; i++ {
show(list[i], n*2)
fmt.Println()
}
}
/* 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(n uint, t tree, sl, pos, rem uint) {
if rem == 0 {
add(t)
return
}
if sl > rem { // need smaller sub-trees
sl = rem
pos = offset[sl]
} else if pos >= offset[sl+1] {
// used up sl-trees, try smaller ones
sl--
if sl == 0 {
return
}
pos = offset[sl]
}
assemble(n, t<<(2*sl)|list[pos], sl, pos, rem-sl)
assemble(n, t, sl, pos+1, rem)
}
func mktrees(n uint) {
if offset[n+1] > 0 {
return
}
if n > 0 {
mktrees(n - 1)
}
assemble(n, 0, n-1, offset[n-1], n-1)
offset[n+1] = uint(len(list))
}
func main() {
if len(os.Args) != 2 {
log.Fatal("There must be exactly 1 command line argument")
}
n, err := strconv.Atoi(os.Args[1])
if err != nil {
log.Fatal("Argument is not a valid number")
}
if n <= 0 || n > 19 { // stack overflow for n == 20
n = 5
}
// init 1-tree
add(0)
mktrees(uint(n))
fmt.Fprintf(os.Stderr, "Number of %d-trees: %d\n", n, offset[n+1]-offset[n])
listTrees(uint(n))
}</syntaxhighlight>
{{out}}
When passing a command line argument of 5:
<pre>
Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())
</pre>
=={{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 266 ⟶ 559:
(()()()())
</pre>
A variant expressed in terms of Data.Tree
<syntaxhighlight lang="haskell">import Data.List (foldl', nub, sortOn) --' strict variant of foldl
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 ixs =
foldl' --' strict variant of foldl
go
(Node 0 [])
(zip [1 .. length ixs] ixs)
where
go tree (i, x) = Node root forest
where
root = rootLabel tree
nest = subForest tree
forest
| root == x = nest <> [Node i []]
| otherwise = (`go` (i, x)) <$> nest</syntaxhighlight>
{{Out}}
<pre>(()()()())
(()()(()))
(()(()()))
((())(()))
(()((())))
((()()()))
((()(())))
(((()())))
((((()))))</pre>
=={{header|J}}==
Line 271 ⟶ 624:
Support code:
<
incr=: ,/@(,"1 0/ i.@{:@$)
boxed=: $:&0 :(<@\:~@([ $:^:(0 < #@]) I.@:=))"1 1 0</
Task:
Line 301 ⟶ 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 307 ⟶ 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 313 ⟶ 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 320 ⟶ 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 334 ⟶ 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.
<syntaxhighlight lang="javascript">(() => {
'use strict';
const main = () =>
bagPatterns(5)
.join('\n');
// BAG PATTERNS ---------------------------------------
// bagPatterns :: Int -> [String]
const bagPatterns = n =>
nub(map(
composeList([
commasFromTree,
depthSortedTree,
treeFromParentIndices
]),
parentIndexPermutations(n)
));
// parentIndexPermutations :: Int -> [[Int]]
const parentIndexPermutations = n =>
sequenceA(
map(curry(enumFromToInt)(0),
enumFromToInt(0, n - 2)
)
);
// treeFromParentIndices :: [Int] -> Tree Int
const treeFromParentIndices = pxs => {
const go = (tree, tplIP) =>
Node(
tree.root,
tree.root === snd(tplIP) ? (
tree.nest.concat(Node(fst(tplIP)), [])
) : map(t => go(t, tplIP), tree.nest)
);
return foldl(
go, Node(0, []),
zip(enumFromToInt(1, pxs.length), pxs)
);
};
// Siblings sorted by descendant count
// depthSortedTree :: Tree a -> Tree Int
const depthSortedTree = t => {
const go = tree =>
isNull(tree.nest) ? (
Node(0, [])
) : (() => {
const xs = map(go, tree.nest);
return Node(
1 + foldl((a, x) => a + x.root, 0, xs),
sortBy(flip(comparing(x => x.root)), xs)
);
})();
return go(t);
};
// Serialisation of the tree structure
// commasFromTree :: Tree a -> String
const commasFromTree = tree => {
const go = t => `(${concat(map(go, t.nest))})`
return go(tree);
};
// GENERIC FUNCTIONS --------------------------------------
// Node :: a -> [Tree a] -> Tree a
const Node = (v, xs) => ({
type: 'Node',
root: v, // any type of value (but must be consistent across tree)
nest: xs || []
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = (a, b) => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
(x, y) => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// composeList :: [(a -> a)] -> (a -> a)
const composeList = fs =>
x => fs.reduceRight((a, f) => f(a), x, fs);
// concat :: [[a]] -> [a]
// concat :: [String] -> String
const concat = xs =>
xs.length > 0 ? (() => {
const unit = typeof xs[0] === 'string' ? '' : [];
return unit.concat.apply(unit, xs);
})() : [];
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = (f, xs) => []
.concat.apply(
[],
(Array.isArray(xs) ? (
xs
) : xs.split('')).map(f)
);
// cons :: a -> [a] -> [a]
const cons = (x, xs) => [x].concat(xs);
// Flexibly handles two or more arguments, applying
// the function directly if the argument array is complete,
// or recursing with a concatenation of any existing and
// newly supplied arguments, if gaps remain.
// curry :: ((a, b) -> c) -> a -> b -> c
const curry = (f, ...args) => {
const go = xs => xs.length >= f.length ? (
f.apply(null, xs)
) : function() {
return go(xs.concat(Array.from(arguments)));
};
return go(args);
};
// enumFromToInt :: Int -> Int -> [Int]
const enumFromToInt = (m, n) =>
n >= m ? (
iterateUntil(x => x >= n, x => 1 + x, m)
) : [];
// flip :: (a -> b -> c) -> b -> a -> c
const flip = f => (a, b) => f.apply(null, [b, a]);
// foldl :: (a -> b -> a) -> a -> [b] -> a
const foldl = (f, a, xs) => xs.reduce(f, a);
// fst :: (a, b) -> a
const fst = tpl => tpl[0];
// isNull :: [a] -> Bool
// isNull :: String -> Bool
const isNull = xs =>
Array.isArray(xs) || typeof xs === 'string' ? (
xs.length < 1
) : undefined;
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
let vs = [x],
h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
// liftA2List :: (a -> b -> c) -> [a] -> [b] -> [c]
const liftA2List = (f, xs, ys) =>
concatMap(x => concatMap(y => [f(x, y)], ys), xs);
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
// nub :: [a] -> [a]
const nub = xs => nubBy((a, b) => a === b, xs);
// nubBy :: (a -> a -> Bool) -> [a] -> [a]
const nubBy = (p, xs) => {
const go = xs => xs.length > 0 ? (() => {
const x = xs[0];
return [x].concat(
go(xs.slice(1)
.filter(y => !p(x, y))
)
)
})() : [];
return go(xs);
};
// sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
const sequenceA = tfa =>
traverseList(x => x, tfa);
// traverseList :: (Applicative f) => (a -> f b) -> [a] -> f [b]
const traverseList = (f, xs) => {
const lng = xs.length;
return 0 < lng ? (() => {
const
vLast = f(xs[lng - 1]),
t = vLast.type || 'List';
return xs.slice(0, -1).reduceRight(
(ys, x) => liftA2List(cons, f(x), ys),
liftA2List(cons, vLast, [[]])
);
})() : [
[]
];
};
// snd :: (a, b) -> b
const snd = tpl => tpl[1];
// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
const sortBy = (f, xs) =>
xs.slice()
.sort(f);
// zip :: [a] -> [b] -> [(a, b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => Tuple(x, ys[i]));
// MAIN ---
return main()
})();</syntaxhighlight>
{{Out}}
<pre>(()()()())
((())()())
((()())())
((())(()))
(((()))())
((()()()))
(((())()))
(((()())))
((((()))))</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}}
<syntaxhighlight 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]))]
bagchain(x, n, bb, start=1) = n < 1 ? [x] :
reduce(append!, [bagchain((x[1] + bb[i][1], x[2] * bb[i][2]),
n - bb[i][1], bb, i) for i in start:length(bb) if bb[i][1] <= n])
for bag in bags(5)
println(bag[2])
end
</syntaxhighlight>{{out}}
<pre>
((((()))))
(((()())))
(((())()))
((()()()))
(((()))())
((()())())
((())(()))
((())()())
(()()()())
</pre>
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.1.3
typealias Tree = Long
val treeList = mutableListOf<Tree>()
val offset = IntArray(32) { if (it == 1) 1 else 0 }
fun append(t: Tree) {
treeList.add(1L or (t shl 1))
}
fun show(t: Tree, l: Int) {
var tt = t
while (ll-- > 0) {
print(if (tt % 2L == 1L) "(" else ")")
tt = tt ushr 1
}
}
fun listTrees(n: Int) {
for (i in offset[n] until offset[n + 1]) {
show(treeList[i], n * 2)
println()
}
}
/* 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
*/
fun assemble(n: Int, t: Tree, sl: Int, pos: Int, rem: Int) {
if (rem == 0) {
append(t)
return
}
var pp = pos
var ss = sl
if (sl > rem) { // need smaller subtrees
ss = rem
pp = offset[ss]
}
else if (pp >= offset[ss + 1]) {
// used up sl-trees, try smaller ones
ss--
if(ss == 0) return
pp = offset[ss]
}
assemble(n, (t shl (2 * ss)) or treeList[pp], ss, pp, rem - ss)
assemble(n, t, ss, pp + 1, rem)
}
fun makeTrees(n: Int) {
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] = treeList.size
}
fun main(args: Array<String>) {
if (args.size != 1) {
throw IllegalArgumentException("There must be exactly 1 command line argument")
}
val n = args[0].toIntOrNull()
if (n == null) throw IllegalArgumentException("Argument is not a valid number")
// n limited to 12 to avoid overflowing default stack
if (n !in 1..12) throw IllegalArgumentException("Argument must be between 1 and 12")
// init 1-tree
append(0)
makeTrees(n)
println("Number of $n-trees: ${offset[n + 1] - offset[n]}")
listTrees(n)
}</syntaxhighlight>
{{out}}
<pre>
Number of 5-trees: 9
(()()()())
</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}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
sub bagchain {
my($x, $n, $bb, $start) = @_;
return [@$x] unless $n;
my @sets;
$start //= 0;
for my $i ($start .. @$bb-1) {
my($c, $s) = @{$$bb[$i]};
push @sets, bagchain([$$x[0] + $c, $$x[1] . $s], $n-$c, $bb, $i) if $c <= $n
}
@sets
}
sub bags {
my($n) = @_;
return [0, ''] unless $n;
my(@upto,@sets);
push @upto, bags($_) for reverse 1 .. $n-1;
for ( bagchain([0, ''], $n-1, \@upto) ) {
my($c,$s) = @$_;
push @sets, [$c+1, '(' . $s . ')']
}
@sets;
}
sub replace_brackets {
my $bags;
my $depth = 0;
for my $b (split //, $_[0]) {
if ($b eq '(') { $bags .= (qw<( [ {>)[$depth++ % 3] }
else { $bags .= (qw<) ] }>)[--$depth % 3] }
}
$bags
}
say replace_brackets $$_[1] for bags(5);</syntaxhighlight>
{{out}}
<pre>([{([])}])
([{()()}])
([{()}{}])
([{}{}{}])
([{()}][])
([{}{}][])
([{}][{}])
([{}][][])
([][][][])</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;">--
-- 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
--</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>
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. 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 400 ⟶ 1,661:
return "".join(out)
for x in bags(5): print(replace_brackets(x[1]))</
{{out}}
<pre>
Line 415 ⟶ 1,676:
Another method by incrementing subtrees:
<
'''
Line 464 ⟶ 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 512 ⟶ 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 525 ⟶ 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>.
<syntaxhighlight 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.*/
if N>5 then do; say N "isn't supported for this program at this time."; exit 13; end
nn= N + N - 1 /*power of 2 that is used for dec start*/
numeric digits 200 /*use enough digs for next calculation.*/
numeric digits max(9, 1 + length( x2b( d2x(2**(nn+1) - 1) ) ) ) /*limit decimal digits.*/
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.*/
@= copies('─', 20)"► "; o = 'o' /*demonstrative literal for solutions. */
#= 0 /*count of ways to nest bags (so far). */
$= /*string holds possible duplicious strs*/
do j=start + start//2 to 2**(nn+1)-1 by 2 /*limit the search, smart start and end*/
t= x2b( d2x(j) ) + 0 /*convert dec number to a binary string*/
z= length( space( translate(t, , 0), 0) ) /*count the number of zeros in bit str.*/
if z\==n then iterate /*Not enough zeroes? Then skip this T.*/
if N>1 then if left(t, N)==right(t, N) then iterate /*left side ≡ right side?*/
if N>2 then if right(t, 2)== 10 then iterate /*has a right─most isolated bag ?*/
if N>3 then if right(t, 4)== 1100 then iterate /* " " " " " */
if N>4 then if right(t, 6)==111000 then iterate /* " " " " " */
if N>4 then if right(t, 6)==110100 then iterate /* " " " " " */
if N>4 then if right(t, 6)==100100 then iterate /* " " " " " */
if wordpos(t, $)\==0 then iterate /*this a duplicate bag stuffing? */
say @ changestr('()', translate(t, "()", 10), o) /*show a compact display with oh.*/
#= # + 1 /*bump count of ways of nesting bags. */
$= $ translate( reverse(t), 01, 10) /*save a (possible) duplicious string. */
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. */</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
────────────────────► (OOOO)
────────────────────► (OO(O))
────────────────────► (O(OO))
────────────────────► (O((O)))
────────────────────► ((O)(O))
────────────────────► ((OOO))
────────────────────► ((O(O)))
────────────────────► (((OO)))
────────────────────► ((((O))))
9 is the number of ways to nest 5 bags.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : List rooted trees
list = "()"
addstr = []
flag = 0
newstr = []
str = []
np = [1,2,3,4]
for nr = 1 to len(np)
if nr = 1
bg1 = "bag"
else
bg1 = "bags"
ok
see "for " + nr + " " + bg1 + " :" + nl
permutation(list,nr*2)
listroot(nr*2)
next
see "ok" + nl
func listroot(pn)
for n = 1 to len(addstr)
result(addstr[n],pn)
if flag = 1
see "" + addstr[n] + nl
addstr[n]
ok
next
func result(list,pn)
flag = 0
newstr = list
while substr(newstr, "()") != 0
if list = "()" or list = "(())"
flag = 1
exit
ok
num = substr(newstr, "()")
newstr = substr(newstr, "()", "")
if left(list,2) = "()" or right(list,2) = "()" or left(list,4) = "(())" or right(list,4) = "(())"
flag = 0
exit
else
if len(list) != 2 and len(list) != 4 and newstr = ""
flag = 1
exit
ok
ok
end
func permutation(list,pn)
addstr = []
while true
str = ""
for n = 1 to pn
rnd = random(1) + 1
str = str + list[rnd]
next
add(addstr,str)
for m = 1 to len(addstr)
for p = m + 1 to len(addstr) - 1
if addstr[m] = addstr[p]
del(addstr,p)
ok
next
next
if len(addstr) = pow(2,pn)
exit
ok
end
</syntaxhighlight>
Output:
<pre>
for 1 bag:
()
for 2 bags:
(())
for 3 bags:
((()))
(()())
for 4 bags:
(()()())
((())())
((()()))
(((())))
</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 566 ⟶ 2,094:
for x in (bags(5)) {
say replace_brackets(x[1])
}</
{{out}}
<pre>
Line 578 ⟶ 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 583 ⟶ 2,200:
Note that "( () (()) () )" the same as "( (()) () () )"
{{trans|Python}}
<
if(not n) return(T(T(0,"")));
Line 615 ⟶ 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>
| |||