Module dyck_word

EXAMPLES:
    sage: from sage.combinat.dyck_word import replace_parens
    sage: replace_parens('(')
    1
    sage: replace_parens(')')
    0
    sage: replace_parens(1)
    Traceback (most recent call last):
    ...
    ValueError

EXAMPLES:
    sage: from sage.combinat.dyck_word import replace_symbols
    sage: replace_symbols(1)
    '('
    sage: replace_symbols(0)
    ')'
    sage: replace_symbols(3)
    Traceback (most recent call last):
    ...
    ValueError

Returns a Dyck word object

EXAMPLES:
    sage: dw = DyckWord([1, 0, 1, 0]); dw
    [1, 0, 1, 0]
    sage: print dw
    ()()
    sage: print dw.height()
    1
    sage: dw.to_noncrossing_partition()
    [[1], [2]]

    sage: DyckWord('()()')
    [1, 0, 1, 0]

    sage: DyckWord(noncrossing_partition=[[1],[2]])
    [1, 0, 1, 0]

Returns the combinatorial class of Dyck words.  A Dyck word is a
sequence $(w_1, ..., w_n)$ consisting of '1's and '0's, with the
property that for any $i$ with $1 \le i \le n$, the sequence
$(w_1,...,w_i)$ contains at least as many $1$s as $0$s.

A Dyck word is balanced if the total number of '1's is equal to the
total number of '0's.  The number of balanced Dyck words of length $2k$
is given by the Catalan number $C_k$.

EXAMPLES:
  If neither k1 nor k2 are specified, then DyckWords returns
  the combinatorial class of all balanced Dyck words.
  
    sage: DW = DyckWords(); DW
    Dyck words
    sage: [] in DW
    True
    sage: [1, 0, 1, 0] in DW
    True
    sage: [1, 1, 0] in DW
    False

  If just k1 is specified, then it returns the combinatorial
  class of balanced Dyck words with k1 opening parentheses and k1
  closing parentheses.
    sage: DW2 = DyckWords(2); DW2
    Dyck words with 2 opening parentheses and 2 closing parentheses
    sage: DW2.first()
    [1, 0, 1, 0]
    sage: DW2.last()
    [1, 1, 0, 0]
    sage: DW2.count()
    2
    sage: DyckWords(100).count() == catalan_number(100)
    True

  If k2 is specified in addition to k1, then it returns
  the combinatorial class of Dyck words with k1 opening
  parentheses and k2 closing parentheses.
    sage: DW32 = DyckWords(3,2); DW32
    Dyck words with 3 opening parentheses and 2 closing parentheses
    sage: DW32.list()
    [[1, 0, 1, 0, 1],
     [1, 0, 1, 1, 0],
     [1, 1, 0, 0, 1],
     [1, 1, 0, 1, 0],
     [1, 1, 1, 0, 0]]

If k1 is specificied, then the object must have exactly k1 open
symbols.  If k2 is also specified, then obj must have exactly
k2 close symbols.

EXAMPLES:
    sage: from sage.combinat.dyck_word import is_a_prefix
    sage: is_a_prefix([1,1,0])
    True
    sage: is_a_prefix([0,1,0])
    False
    sage: is_a_prefix([1,1,0],2,1)
    True
    sage: is_a_prefix([1,1,0],1,1)
    False

If k1 is specificied, then the object must have exactly k1 open
symbols.  If k2 is also specified, then obj must have exactly
k2 close symbols.

EXAMPLES:
    sage: from sage.combinat.dyck_word import is_a
    sage: is_a([1,1,0,0])
    True
    sage: is_a([1,0,1,0])
    True
    sage: is_a([1,1,0,0],2)
    True
    sage: is_a([1,1,0,0],3)
    False

TESTS:
    sage: DyckWord(noncrossing_partition=[[1,2]]) # indirect doctest
    [1, 1, 0, 0]
    sage: DyckWord(noncrossing_partition=[[1],[2]])
    [1, 0, 1, 0]

    sage: dws = DyckWords(5).list()
    sage: ncps = map( lambda x: x.to_noncrossing_partition(), dws)
    sage: dws2 = map( lambda x: DyckWord(noncrossing_partition=x), ncps)
    sage: dws == dws2
    True

TESTS:
    sage: sage.combinat.dyck_word.from_ordered_tree(1)
    Traceback (most recent call last):
    ...
    NotImplementedError: TODO