Anonymous user
List rooted trees: Difference between revisions
→{{header|REXX}}: added the REXX computer programming language.
(→{{header|Haskell}}: Added a Haskell variant which uses Data.Tree) |
(→{{header|REXX}}: added the REXX computer programming language.) |
||
Line 1,040:
((((()))))
#t</pre>
=={{header|REXX}}==
<lang rexx>/*REXX program lists n─node rooted trees (by enumerating all ways of nesting N bato).*/
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 /*ensure enough digs for the next calc.*/
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)"► " /*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 /*duplicate bag stuffing?*/
say _ changestr('()', translate(t, "()", 10), 'O') /*show a compact display.*/
#= # + 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. */</lang>
{{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}}==
| |||