ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 23 Dec 2015 11:53:59 +0100How to compute the set of Dyck paths ?https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/ I am new to SAGE and try to experiment with it. So I apologize if my question is too trivial. I am interested to do Dyck paths with SAGE. I understand that
D=DyckWords(n)
D.list()
gives Dyck words as 2n-tuples of n numbers 0,1. But I want to get the corresponding Dyck paths by replacing 1 with an up-step (1,1) and 0 with a down-step (1,-1) represented by the (2n+1)-tuple of the heights of the path.
Thus instead of w=[1,1,1,0,0,1,0,0] I want d=[0,1,2,3,2,1,2,1,0] with height h(d)=3.
How do I get this? And how to compute the height of the path? More precisely how to compute the set of all (d,h(d))for d in D?
Tue, 22 Dec 2015 16:38:20 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/Answer by tmonteil for <p>I am new to SAGE and try to experiment with it. So I apologize if my question is too trivial. I am interested to do Dyck paths with SAGE. I understand that </p>
<p>D=DyckWords(n)</p>
<p>D.list()</p>
<p>gives Dyck words as 2n-tuples of n numbers 0,1. But I want to get the corresponding Dyck paths by replacing 1 with an up-step (1,1) and 0 with a down-step (1,-1) represented by the (2n+1)-tuple of the heights of the path.</p>
<p>Thus instead of w=[1,1,1,0,0,1,0,0] I want d=[0,1,2,3,2,1,2,1,0] with height h(d)=3.</p>
<p>How do I get this? And how to compute the height of the path? More precisely how to compute the set of all (d,h(d))for d in D?</p>
https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?answer=31756#post-id-31756As you can see, `d` is a kind of discrete primitive of `w`. So you can compute it as follows:
sage: def primitive(w):
....: height = 0
....: d = [height]
....: for i in w:
....: if i == 1:
....: height += 1
....: d.append(height)
....: else:
....: height -= 1
....: d.append(height)
....: return d
sage: w=[1,1,1,0,0,1,0,0]
sage: primitive(w)
[0, 1, 2, 3, 2, 1, 2, 1, 0]
You can get its height as follows:
sage: max(primitive(w))
3
You can get all primitives of all Dyck words of a given length as follows:
sage: [primitive(w) for w in DyckWords(4)]
[[0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 1, 0, 1, 0],
[0, 1, 0, 1, 2, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 1, 0, 1, 0, 1, 0],
[0, 1, 2, 1, 0, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 1, 0, 1, 0],
[0, 1, 2, 1, 2, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 2, 1, 0, 1, 0],
[0, 1, 2, 3, 2, 1, 2, 1, 0],
[0, 1, 2, 3, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 4, 3, 2, 1, 0]]
Hence you can get the set of heights as follows:
sage: {max(primitive(w)) for w in DyckWords(4)}
{1, 2, 3, 4}
Tue, 22 Dec 2015 17:44:23 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?answer=31756#post-id-31756Comment by hans for <p>As you can see, <code>d</code> is a kind of discrete primitive of <code>w</code>. So you can compute it as follows:</p>
<pre><code>sage: def primitive(w):
....: height = 0
....: d = [height]
....: for i in w:
....: if i == 1:
....: height += 1
....: d.append(height)
....: else:
....: height -= 1
....: d.append(height)
....: return d
sage: w=[1,1,1,0,0,1,0,0]
sage: primitive(w)
[0, 1, 2, 3, 2, 1, 2, 1, 0]
</code></pre>
<p>You can get its height as follows:</p>
<pre><code>sage: max(primitive(w))
3
</code></pre>
<p>You can get all primitives of all Dyck words of a given length as follows:</p>
<pre><code>sage: [primitive(w) for w in DyckWords(4)]
[[0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 1, 0, 1, 0],
[0, 1, 0, 1, 2, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 1, 0, 1, 0, 1, 0],
[0, 1, 2, 1, 0, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 1, 0, 1, 0],
[0, 1, 2, 1, 2, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 2, 1, 0, 1, 0],
[0, 1, 2, 3, 2, 1, 2, 1, 0],
[0, 1, 2, 3, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 4, 3, 2, 1, 0]]
</code></pre>
<p>Hence you can get the set of heights as follows:</p>
<pre><code>sage: {max(primitive(w)) for w in DyckWords(4)}
{1, 2, 3, 4}
</code></pre>
https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31785#post-id-31785Thank you very much.
I would also like to know where I can find more about lattice paths in SAGE, e.g. how to compute number of peaks or valleys, Motzkin paths, etc.Wed, 23 Dec 2015 09:32:53 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31785#post-id-31785Answer by vdelecroix for <p>I am new to SAGE and try to experiment with it. So I apologize if my question is too trivial. I am interested to do Dyck paths with SAGE. I understand that </p>
<p>D=DyckWords(n)</p>
<p>D.list()</p>
<p>gives Dyck words as 2n-tuples of n numbers 0,1. But I want to get the corresponding Dyck paths by replacing 1 with an up-step (1,1) and 0 with a down-step (1,-1) represented by the (2n+1)-tuple of the heights of the path.</p>
<p>Thus instead of w=[1,1,1,0,0,1,0,0] I want d=[0,1,2,3,2,1,2,1,0] with height h(d)=3.</p>
<p>How do I get this? And how to compute the height of the path? More precisely how to compute the set of all (d,h(d))for d in D?</p>
https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?answer=31764#post-id-31764A one line conversion
sage: w = [1,1,1,0,0,1,0,0]
sage: for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1
sage: print w
[1, 2, 3, 2, 1, 2, 1, 0]
Tue, 22 Dec 2015 21:36:04 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?answer=31764#post-id-31764Comment by hans for <p>A one line conversion</p>
<pre><code>sage: w = [1,1,1,0,0,1,0,0]
sage: for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1
sage: print w
[1, 2, 3, 2, 1, 2, 1, 0]
</code></pre>
https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31786#post-id-31786Thank you very much. I wanted to do the same as in the second answer:
def prim(w):
for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1
[prim(w) for w in DyckWords(4)]
but got
TypeError: 'CompleteDyckWords_size_with_category.element_class' object does not support item assignment.
How can this be corrected?Wed, 23 Dec 2015 09:39:11 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31786#post-id-31786Comment by vdelecroix for <p>A one line conversion</p>
<pre><code>sage: w = [1,1,1,0,0,1,0,0]
sage: for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1
sage: print w
[1, 2, 3, 2, 1, 2, 1, 0]
</code></pre>
https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31789#post-id-31789Yes. Dyck words are not list (even though they are printed as such). You need to convert them to list first
sage: d = DyckWords(5).an_element()
sage: print d
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sage: print type(d)
<class 'sage.combinat.dyck_word.CompleteDyckWords_size_with_category.element_class'>
sage: l = list(d)
sage: print type(l)
<type 'list'>
sage: print l
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]Wed, 23 Dec 2015 11:53:59 +0100https://ask.sagemath.org/question/31755/how-to-compute-the-set-of-dyck-paths/?comment=31789#post-id-31789