List rooted trees: Difference between revisions

{{trans|Python}}

 

I n == 0

R [x]

 

L(x) bags(5)

 

{{out}}

=={{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>

 

 

return 0;

{{out}}

<pre>

=={{header|C++}}==

{{trans|Java}}

#include <vector>

 

 

return 0;

{{out}}

<pre>Number of 5-trees: 9

=={{header|D}}==

{{trans|C}}

 

alias Tree = ulong,

stderr.writefln("Number of %d-trees: %u", n, offset[n + 1] - offset[n]);

listTees(n, offset, list);

{{out}}

<pre>Number of 5-trees: 9

=={{header|Go}}==

{{trans|C}}

 

import (

fmt.Fprintf(os.Stderr, "Number of %d-trees: %d\n", n, offset[n+1]-offset[n])

listTrees(uint(n))

 

{{out}}

=={{header|Haskell}}==

There probably is a nicer way than the following--

parts :: Int -> [[(Int, Int)]]

parts n = f n 1

 

main :: IO ()

{{out}}

<pre>

A variant expressed in terms of Data.Tree

 

import Data.Ord (comparing)

import Data.Tree (Tree (..), foldTree)

forest

| root == x = nest <> [Node i []]

{{Out}}

<pre>(()()()())

Support code:

 

incr=: ,/@(,"1 0/ i.@{:@$)

 

 

Task:

So, for example, here is what some intermediate results would look like for the four bag case:

 

_ 0 0 0

_ 0 0 1

_ 0 1 0

_ 0 1 1

 

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.)

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

(()()())

((())())

((()()))

 

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:

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.List;

 

test(5);

}

{{out}}

<pre>Number of 5-trees: 9

===ES6===

Composing a solution from generic functions.

'use strict';

 

// MAIN ---

return main()

{{Out}}

<pre>(()()()())

(((()())))

((((()))))</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]))]

println(bag[2])

end

<pre>

((((()))))

=={{header|Kotlin}}==

{{trans|C}}

 

typealias Tree = Long

println("Number of $n-trees: ${offset[n + 1] - offset[n]}")

listTrees(n)

 

{{out}}

=={{header|Lua}}==

{{trans|Java}}

offset = {}

 

 

init()

{{out}}

<pre>Number of 5-trees: 9

(()()(()))

(()()()())</pre>

 

=={{header|Nim}}==

{{trans|Kotlin}}

 

type

trees.make(n)

echo &"Number of {n}-trees: {trees.offsets[n + 1] - trees.offsets[n]}"

 

{{out}}

=={{header|Perl}}==

{{trans|Sidef}}

use warnings;

use feature 'say';

}

 

{{out}}

<pre>([{([])}])

=={{header|Phix}}==

{{trans|Go}}

{{out}}

<pre>

Number of 20-trees: 12,826,228 (13.6s)

</pre>

 

=={{header|Python}}==

if not n: return [(0, "")]

 

return "".join(out)

 

{{out}}

<pre>

 

Another method by incrementing subtrees:

 

'''

def tostr(x): return "(" + "".join(map(tostr, x)) + ")"

 

 

=={{header|Racket}}==

(require racket/splicing data/order)

 

(for-each displayln (LRTs 5))

(equal? (map (compose length LRTs) (range 1 (add1 13)))

 

{{out}}

Bags are represented by Raku type [http://doc.raku.org/type/Bag <code>Bag</code>].

 

 

multi expand-tree ( Bag $tree ) {

.say

};

{{out}}

<pre>

=={{header|REXX}}==

This REXX version uses (internally) a binary string to represent nodes on a tree &nbsp; (<big>'''0'''</big> &nbsp; is a left parenthesis, &nbsp; <big>'''1'''</big> &nbsp; is a right parenthesis). &nbsp; A &nbsp; <big>'''()'''</big> &nbsp; is translated to a &nbsp; <big>'''O'''</big>.

parse arg N . /*obtain optional argument from the CL.*/

if N=='' | N=="," then N=5 /*Not specified? Then use the default.*/

end /*j*/

say /*separate number─of─ways with a blank.*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

# Project : List rooted trees

 

ok

end

Output:

<pre>

=={{header|Ruby}}==

{{trans|Java}}

OFFSET = []

 

end

 

{{out}}

<pre>Number of 5-trees: 9

=={{header|Sidef}}==

{{trans|Python}}

n || return [x]

 

for x in (bags(5)) {

say replace_brackets(x[1])

{{out}}

<pre>

{{trans|Kotlin}}

{{libheader|Wren-long}}

import "os" for Process

 

makeTrees.call(n)

System.print("Number of %(n)-trees: %(offset[n + 1] - offset[n])")

 

{{out}}

Note that "( () (()) () )" the same as "( (()) () () )"

{{trans|Python}}

if(not n) return(T(T(0,"")));

 

foreach x in (bags(5)){ println(replace_brackets(x[1])) }

println("or");

{{out}}

<pre>