List rooted trees: Difference between revisions

 

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.

As an example output, run 5 bags.   There should be 9 ways.

<br><br>

 

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

(()()()())

</pre>

 

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

 

-- choose n strings out of a list and join them

pick _ [] = []

pick 0 _ = [""]

 

 

{{out}}

<pre>

</pre>

 

 

import Data.Ord (comparing)

 

bagPatterns :: Int -> [String]

bagPatterns n =

nub $

 

parentIndexPermutations :: Int -> [[Int]]

parentIndexPermutations =

 

treeFromParentIndices :: [Int] -> Tree Int

foldl' --' strict variant of foldl

go

(Node 0 [])

where

{{Out}}

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

((())(()))

((()()()))

(((()())))

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

│ │ │ │ │ │└────┘│

└────┴─────┴─────┴─────┴─────┴──────┘</pre>

 

=={{header|Javascript}}==

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

((((()))))

(()()()())

</pre>

 

=={{header|Kotlin}}==

{{trans|C}}

 

typealias Tree = Long

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

listTrees(n)

 

{{out}}

</pre>

 

 

 

}

 

 

{{out}}

 

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

((((()))))

#t</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.*/

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 max(9, 1 + length( x2b( d2x(2**(nn+1) - 1) ) ) ) /*limit decimal digits.*/

if N==1 then start= 2**1 /*treat the start for unity as special.*/

$= /*string holds possible duplicious strs*/

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>

(((())))

</pre>

 

=={{header|Sidef}}==

{{trans|Python}}

n || return [x]

 

for x in (bags(5)) {

say replace_brackets(x[1])

{{out}}

<pre>

([{}][][])

([][][][])

</pre>

 

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>