combinat-0.1: Generation of various combinatorial objects.

Math.Combinat.Trees

Description

Trees, forests, etc. See: Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 4A.

Synopsis

# Types

data BinTree a Source

Constructors

 Branch (BinTree a) (BinTree a) Leaf a

Instances

 Eq a => Eq (BinTree a) Ord a => Ord (BinTree a) Read a => Read (BinTree a) Show a => Show (BinTree a)

module Data.Tree

data Paren Source

Constructors

 LeftParen RightParen

Instances

 Eq Paren Ord Paren Read Paren Show Paren

# Nested parentheses

nestedParentheses :: Int -> [[Paren]]Source

Synonym for fasc4A_algorithm_P.

fasc4A_algorithm_P :: Int -> [[Paren]]Source

Generates all sequences of nested parentheses of length 2n. Order is lexigraphic (when right parentheses are considered smaller then left ones). Based on "Algorithm P" in Knuth, but less efficient because of the "idiomatic" code.

# Binary trees

Generates all binary trees with n nodes.

# = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }.

This is also the counting function for forests and nested parentheses.

Generates all binary trees with n nodes. The naive algorithm.