ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 11 Nov 2017 08:25:27 -0600tree of vectorshttp://ask.sagemath.org/question/39425/tree-of-vectors/This is a more complicated version of
[apply functions iteratively](https://ask.sagemath.org/question/36159/apply-functions-iteratively-modified-re-post/)
I have a starting "seed" vector, say
`e1 = matrix(4,1,(1,0,0,0))`
Next, I have a collection of 4x4 matrices
`thin_group = [T1,T2,T3,T4,T5]`
where
$T1 = \left(\begin{array}{rrrr}
-1 & 0 & 0 & 0 \\\\
2 & 1 & 0 & 0 \\\\
4 & 0 & 1 & 0 \\\\
4 & 0 & 0 & 1
\end{array}\right), T2 = \left(\begin{array}{rrrr}
1 & 2 & 0 & 0 \\\\
0 & -1 & 0 & 0 \\\\
0 & 4 & 1 & 0 \\\\
0 & 4 & 0 & 1
\end{array}\right), T3 = \left(\begin{array}{rrrr}
1 & 0 & 1 & 0 \\\\
0 & 1 & 1 & 0 \\\\
0 & 0 & -1 & 0 \\\\
0 & 0 & 0 & 1
\end{array}\right), T4 = \left(\begin{array}{rrrr}
1 & 6 & 0 & 6 \\\\
0 & 3 & 0 & 2 \\\\
0 & 4 & 1 & 4 \\\\
0 & -4 & 0 & -3
\end{array}\right), T5 = \left(\begin{array}{rrrr}
3 & 0 & 0 & 2 \\\\
6 & 1 & 0 & 6 \\\\
4 & 0 & 1 & 4 \\\\
-4 & 0 & 0 & -3
\end{array}\right)$
These matrices either fix `e1` or send to a different vector. I have a "height" function, which just measures how large the vector entries are getting.
`def h(X):
return max(abs(X[0,0],abs(X[1,0]), abs(X[2,0]),abs(X[3,0]))`
I want to develop the following procedure:
`hmax = 50`
Begin applying T1,...,T5 to e1. As soon as I get a different vector (T1*e1 = (-1,2,4,4)), measure the height of that vector. If the height is below hmax (h(-1,2,4,4) = 4 < hmax = 50), store that vector somewhere. Now apply another matrix from thin_group to (-1,2,4,4), (but not T1 again). If the new vector has a height below hmax, store it, and apply another matrix from thin_group, just not the previous one. Continue this process until we reach a vector with a height larger than hmax. Once this happens, go back to the previous vector and apply a different matrix from thin_group i.e. go up a different branch of the tree. Go up this branch until hmax is exceeded, then go up a different branch, etc.. Eventually, this process will generate all thin_group images of e1 with hmax < 50. (this is probably about 50,000 vectors)
This procedure should "remember" the vectors that were counted/stored, so I'm thinking that I may be able to index each vector in the tree with a sequence (a1,a2,a3,...,an) where aj=1,2,3,4,5 to denote which matrix T1,...,T5 we applied previously.
Any/all ideas or partial solutions greatly appreciated. Thanks!Tue, 07 Nov 2017 12:01:32 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/Answer by Sébastien for <p>This is a more complicated version of
<a href="https://ask.sagemath.org/question/36159/apply-functions-iteratively-modified-re-post/">apply functions iteratively</a> </p>
<p>I have a starting "seed" vector, say
<code>e1 = matrix(4,1,(1,0,0,0))</code>
Next, I have a collection of 4x4 matrices</p>
<p><code>thin_group = [T1,T2,T3,T4,T5]</code></p>
<p>where</p>
<p>$T1 = \left(\begin{array}{rrrr}
-1 & 0 & 0 & 0 \\
2 & 1 & 0 & 0 \\
4 & 0 & 1 & 0 \\
4 & 0 & 0 & 1
\end{array}\right), T2 = \left(\begin{array}{rrrr}
1 & 2 & 0 & 0 \\
0 & -1 & 0 & 0 \\
0 & 4 & 1 & 0 \\
0 & 4 & 0 & 1
\end{array}\right), T3 = \left(\begin{array}{rrrr}
1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 1
\end{array}\right), T4 = \left(\begin{array}{rrrr}
1 & 6 & 0 & 6 \\
0 & 3 & 0 & 2 \\
0 & 4 & 1 & 4 \\
0 & -4 & 0 & -3
\end{array}\right), T5 = \left(\begin{array}{rrrr}
3 & 0 & 0 & 2 \\
6 & 1 & 0 & 6 \\
4 & 0 & 1 & 4 \\
-4 & 0 & 0 & -3
\end{array}\right)$</p>
<p>These matrices either fix <code>e1</code> or send to a different vector. I have a "height" function, which just measures how large the vector entries are getting.</p>
<p><code>def h(X):
return max(abs(X[0,0],abs(X[1,0]), abs(X[2,0]),abs(X[3,0]))</code></p>
<p>I want to develop the following procedure:</p>
<p><code>hmax = 50</code>
Begin applying T1,...,T5 to e1. As soon as I get a different vector (T1*e1 = (-1,2,4,4)), measure the height of that vector. If the height is below hmax (h(-1,2,4,4) = 4 < hmax = 50), store that vector somewhere. Now apply another matrix from thin_group to (-1,2,4,4), (but not T1 again). If the new vector has a height below hmax, store it, and apply another matrix from thin_group, just not the previous one. Continue this process until we reach a vector with a height larger than hmax. Once this happens, go back to the previous vector and apply a different matrix from thin_group i.e. go up a different branch of the tree. Go up this branch until hmax is exceeded, then go up a different branch, etc.. Eventually, this process will generate all thin_group images of e1 with hmax < 50. (this is probably about 50,000 vectors)</p>
<p>This procedure should "remember" the vectors that were counted/stored, so I'm thinking that I may be able to index each vector in the tree with a sequence (a1,a2,a3,...,an) where aj=1,2,3,4,5 to denote which matrix T1,...,T5 we applied previously. </p>
<p>Any/all ideas or partial solutions greatly appreciated. Thanks!</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?answer=39428#post-id-39428I think you want to use [RecursivelyEnumeratedSet](http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#) in sage which consist in applying iteratively a successor function to a set of initial seeds:
sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
To get a finite set, you may want to use `max_depth` as above or `hmax` as you suggest:
sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:
sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
The above numbers confirm what dan_fulea obtain.
Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):
sage -pip install slabbe
sage -i dot2tex
and then:
sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
![image description](/upfiles/15100902665102815.png)
Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use
sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use
sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
which will allow you to enumerate the vectors in parallel using fast [map reduce algorithms written by Florent Hivert](http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html) without keeping the elements in memory. In any case, first consult the documentation I have written:
sage: RecursivelyEnumeratedSet?
One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:
sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
![graph with labels indicating which matrix was used](/upfiles/15100939649572804.png)
I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.Tue, 07 Nov 2017 14:22:51 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?answer=39428#post-id-39428Comment by Sébastien for <p>I think you want to use <a href="http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#">RecursivelyEnumeratedSet</a> in sage which consist in applying iteratively a successor function to a set of initial seeds:</p>
<pre><code>sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
</code></pre>
<p>To get a finite set, you may want to use <code>max_depth</code> as above or <code>hmax</code> as you suggest:</p>
<pre><code>sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
</code></pre>
<p>The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:</p>
<pre><code>sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
</code></pre>
<p>The above numbers confirm what dan_fulea obtain.</p>
<p>Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):</p>
<pre><code>sage -pip install slabbe
sage -i dot2tex
</code></pre>
<p>and then:</p>
<pre><code>sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
</code></pre>
<p><img alt="image description" src="/upfiles/15100902665102815.png"></p>
<p>Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
</code></pre>
<p>which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
</code></pre>
<p>which will allow you to enumerate the vectors in parallel using fast <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html">map reduce algorithms written by Florent Hivert</a> without keeping the elements in memory. In any case, first consult the documentation I have written:</p>
<pre><code>sage: RecursivelyEnumeratedSet?
</code></pre>
<p>One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:</p>
<pre><code>sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
</code></pre>
<p><img alt="graph with labels indicating which matrix was used" src="/upfiles/15100939649572804.png"></p>
<p>I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39499#post-id-39499Maybe it depends on the way you use Sage?
On the terminal, it works for me. Also in the ipython notebook, you may try:
tikz = TikzPicture.from_graph(G)
path_to_file = tikz.png()
from ipython.display import Image
Image(path_to_file)Sat, 11 Nov 2017 08:25:27 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39499#post-id-39499Comment by Daniel L for <p>I think you want to use <a href="http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#">RecursivelyEnumeratedSet</a> in sage which consist in applying iteratively a successor function to a set of initial seeds:</p>
<pre><code>sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
</code></pre>
<p>To get a finite set, you may want to use <code>max_depth</code> as above or <code>hmax</code> as you suggest:</p>
<pre><code>sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
</code></pre>
<p>The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:</p>
<pre><code>sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
</code></pre>
<p>The above numbers confirm what dan_fulea obtain.</p>
<p>Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):</p>
<pre><code>sage -pip install slabbe
sage -i dot2tex
</code></pre>
<p>and then:</p>
<pre><code>sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
</code></pre>
<p><img alt="image description" src="/upfiles/15100902665102815.png"></p>
<p>Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
</code></pre>
<p>which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
</code></pre>
<p>which will allow you to enumerate the vectors in parallel using fast <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html">map reduce algorithms written by Florent Hivert</a> without keeping the elements in memory. In any case, first consult the documentation I have written:</p>
<pre><code>sage: RecursivelyEnumeratedSet?
</code></pre>
<p>One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:</p>
<pre><code>sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
</code></pre>
<p><img alt="graph with labels indicating which matrix was used" src="/upfiles/15100939649572804.png"></p>
<p>I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39467#post-id-39467On the last line `tikz.pdf()`, I don't get any output. I have dot2tex, graphviz, and slabbe installed. Any idea why this may be so?Thu, 09 Nov 2017 14:31:28 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39467#post-id-39467Comment by Daniel L for <p>I think you want to use <a href="http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#">RecursivelyEnumeratedSet</a> in sage which consist in applying iteratively a successor function to a set of initial seeds:</p>
<pre><code>sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
</code></pre>
<p>To get a finite set, you may want to use <code>max_depth</code> as above or <code>hmax</code> as you suggest:</p>
<pre><code>sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
</code></pre>
<p>The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:</p>
<pre><code>sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
</code></pre>
<p>The above numbers confirm what dan_fulea obtain.</p>
<p>Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):</p>
<pre><code>sage -pip install slabbe
sage -i dot2tex
</code></pre>
<p>and then:</p>
<pre><code>sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
</code></pre>
<p><img alt="image description" src="/upfiles/15100902665102815.png"></p>
<p>Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
</code></pre>
<p>which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
</code></pre>
<p>which will allow you to enumerate the vectors in parallel using fast <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html">map reduce algorithms written by Florent Hivert</a> without keeping the elements in memory. In any case, first consult the documentation I have written:</p>
<pre><code>sage: RecursivelyEnumeratedSet?
</code></pre>
<p>One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:</p>
<pre><code>sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
</code></pre>
<p><img alt="graph with labels indicating which matrix was used" src="/upfiles/15100939649572804.png"></p>
<p>I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39435#post-id-39435Ok got it. In some cases, my thin_group may have loops and in other cases not. The visualization is very nice!Tue, 07 Nov 2017 16:18:12 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39435#post-id-39435Comment by Sébastien for <p>I think you want to use <a href="http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#">RecursivelyEnumeratedSet</a> in sage which consist in applying iteratively a successor function to a set of initial seeds:</p>
<pre><code>sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
</code></pre>
<p>To get a finite set, you may want to use <code>max_depth</code> as above or <code>hmax</code> as you suggest:</p>
<pre><code>sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
</code></pre>
<p>The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:</p>
<pre><code>sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
</code></pre>
<p>The above numbers confirm what dan_fulea obtain.</p>
<p>Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):</p>
<pre><code>sage -pip install slabbe
sage -i dot2tex
</code></pre>
<p>and then:</p>
<pre><code>sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
</code></pre>
<p><img alt="image description" src="/upfiles/15100902665102815.png"></p>
<p>Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
</code></pre>
<p>which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
</code></pre>
<p>which will allow you to enumerate the vectors in parallel using fast <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html">map reduce algorithms written by Florent Hivert</a> without keeping the elements in memory. In any case, first consult the documentation I have written:</p>
<pre><code>sage: RecursivelyEnumeratedSet?
</code></pre>
<p>One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:</p>
<pre><code>sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
</code></pre>
<p><img alt="graph with labels indicating which matrix was used" src="/upfiles/15100939649572804.png"></p>
<p>I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39433#post-id-39433That was my first attempt. I edited my answer later on using your matrices instead of random ones, but I forgot at some point to edit that line. It should be ok now.Tue, 07 Nov 2017 15:52:26 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39433#post-id-39433Comment by Daniel L for <p>I think you want to use <a href="http://doc.sagemath.org/html/en/reference/sets/sage/sets/recursively_enumerated_set.html#">RecursivelyEnumeratedSet</a> in sage which consist in applying iteratively a successor function to a set of initial seeds:</p>
<pre><code>sage: v = matrix(4,1,(1,0,0,0))
sage: v.set_immutable()
sage: seed = [v]
sage: T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
sage: T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
sage: T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
sage: T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
sage: T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
sage: thin_group = [T1, T2, T3, T4, T5]
sage: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: ans.append(m_u)
....: return ans
....:
sage: R = RecursivelyEnumeratedSet(seed, succ, max_depth=4)
sage: R
A recursively enumerated set (breadth first search) with max_depth=4
</code></pre>
<p>To get a finite set, you may want to use <code>max_depth</code> as above or <code>hmax</code> as you suggest:</p>
<pre><code>sage: def the_rec_enum_set(hmax):
....: def succ(u):
....: ans = []
....: for m in thin_group:
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append(m_u)
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: the_rec_enum_set(20)
A recursively enumerated set (breadth first search)
</code></pre>
<p>The recursively enumerated set can be enumerated in different maner (look at the documentation). What I like the most is to create the generated graph:</p>
<pre><code>sage: G = the_rec_enum_set(20).to_digraph(); G
Looped multi-digraph on 10 vertices
sage: G = the_rec_enum_set(50).to_digraph(); G
Looped multi-digraph on 37 vertices
sage: G = the_rec_enum_set(500).to_digraph(); G
Looped multi-digraph on 775 vertices
</code></pre>
<p>The above numbers confirm what dan_fulea obtain.</p>
<p>Then, you may want to use my optional package to visualize it (with dot2tex and graphviz installed):</p>
<pre><code>sage -pip install slabbe
sage -i dot2tex
</code></pre>
<p>and then:</p>
<pre><code>sage: from slabbe import TikzPicture
sage: G = the_rec_enum_set(20).to_digraph()
sage: tikz = TikzPicture.from_graph(G)
sage: tikz.pdf() # or tikz.png() or tikz.svg()
</code></pre>
<p><img alt="image description" src="/upfiles/15100902665102815.png"></p>
<p>Looking at the picture, your structure looks to be symmetric (y is a successor of x if and only if x is a successor of y). If so, use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='symmetric')
</code></pre>
<p>which allows to enumerate all elements without keeping all of them in memory. Even better, if your structure is really a tree or a forest (that is if you are able to avoid backward arrows and any loop in the successor function), then use</p>
<pre><code>sage: R = RecursivelyEnumeratedSet(seed, succ, structure='forest')
</code></pre>
<p>which will allow you to enumerate the vectors in parallel using fast <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html">map reduce algorithms written by Florent Hivert</a> without keeping the elements in memory. In any case, first consult the documentation I have written:</p>
<pre><code>sage: RecursivelyEnumeratedSet?
</code></pre>
<p>One information that is missing in the graph is the label of the edges. One way to solve this is to momentarily hide the label information inside the arrival vertex. Once, the graph is made, we put back the information into the edge. I usually do like this:</p>
<pre><code>sage: seed = [(v,None)]
sage: def the_rec_enum_set(hmax):
....: def succ(node):
....: u,label = node
....: ans = []
....: for i,m in zip([1,2,3,4,5], thin_group):
....: m_u = m*u
....: m_u.set_immutable()
....: if max(map(abs, m_u)) < hmax:
....: ans.append((m_u,i))
....: return ans
....: R = RecursivelyEnumeratedSet(seed, succ)
....: return R
....:
sage: R = the_rec_enum_set(20)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 22 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: GG = digraph_move_label_to_edge(G)
sage: GG
Looped digraph on 10 vertices
sage: TikzPicture.from_graph(GG).pdf()
</code></pre>
<p><img alt="graph with labels indicating which matrix was used" src="/upfiles/15100939649572804.png"></p>
<p>I intend to move this feature directly in Sage once I have time. Tell me if you have any other comment, I intend to improve this module in a near future.</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39432#post-id-39432Very nice code, thank you.
Can I ask, in line 4, why did you use random matrices?Tue, 07 Nov 2017 15:49:01 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39432#post-id-39432Answer by dan_fulea for <p>This is a more complicated version of
<a href="https://ask.sagemath.org/question/36159/apply-functions-iteratively-modified-re-post/">apply functions iteratively</a> </p>
<p>I have a starting "seed" vector, say
<code>e1 = matrix(4,1,(1,0,0,0))</code>
Next, I have a collection of 4x4 matrices</p>
<p><code>thin_group = [T1,T2,T3,T4,T5]</code></p>
<p>where</p>
<p>$T1 = \left(\begin{array}{rrrr}
-1 & 0 & 0 & 0 \\
2 & 1 & 0 & 0 \\
4 & 0 & 1 & 0 \\
4 & 0 & 0 & 1
\end{array}\right), T2 = \left(\begin{array}{rrrr}
1 & 2 & 0 & 0 \\
0 & -1 & 0 & 0 \\
0 & 4 & 1 & 0 \\
0 & 4 & 0 & 1
\end{array}\right), T3 = \left(\begin{array}{rrrr}
1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 1
\end{array}\right), T4 = \left(\begin{array}{rrrr}
1 & 6 & 0 & 6 \\
0 & 3 & 0 & 2 \\
0 & 4 & 1 & 4 \\
0 & -4 & 0 & -3
\end{array}\right), T5 = \left(\begin{array}{rrrr}
3 & 0 & 0 & 2 \\
6 & 1 & 0 & 6 \\
4 & 0 & 1 & 4 \\
-4 & 0 & 0 & -3
\end{array}\right)$</p>
<p>These matrices either fix <code>e1</code> or send to a different vector. I have a "height" function, which just measures how large the vector entries are getting.</p>
<p><code>def h(X):
return max(abs(X[0,0],abs(X[1,0]), abs(X[2,0]),abs(X[3,0]))</code></p>
<p>I want to develop the following procedure:</p>
<p><code>hmax = 50</code>
Begin applying T1,...,T5 to e1. As soon as I get a different vector (T1*e1 = (-1,2,4,4)), measure the height of that vector. If the height is below hmax (h(-1,2,4,4) = 4 < hmax = 50), store that vector somewhere. Now apply another matrix from thin_group to (-1,2,4,4), (but not T1 again). If the new vector has a height below hmax, store it, and apply another matrix from thin_group, just not the previous one. Continue this process until we reach a vector with a height larger than hmax. Once this happens, go back to the previous vector and apply a different matrix from thin_group i.e. go up a different branch of the tree. Go up this branch until hmax is exceeded, then go up a different branch, etc.. Eventually, this process will generate all thin_group images of e1 with hmax < 50. (this is probably about 50,000 vectors)</p>
<p>This procedure should "remember" the vectors that were counted/stored, so I'm thinking that I may be able to index each vector in the tree with a sequence (a1,a2,a3,...,an) where aj=1,2,3,4,5 to denote which matrix T1,...,T5 we applied previously. </p>
<p>Any/all ideas or partial solutions greatly appreciated. Thanks!</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?answer=39429#post-id-39429My generating statistics differs, so i hope i understood the question well. Here is the quick code:
T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
T_List = ( T1, T2, T3, T4, T5 )
v = vector( ZZ, 4, [ 1,0,0,0 ] )
v = v.column()
def ht( w ):
return max( [ abs(entry) for entry in w ] )
def fillList( T_List, vector_List, height ):
v_List = vector_List[:] # and we will append
v_New = vector_List[:] # use them to generate new vectors, this is the "last wave"
count = 0 # give me some small control...
while v_New and count < 100 :
count += 1 # this will protect me against the usual programming errors
w_New = [] # and we will append, this is the "new wave"
for v in v_New:
for T in T_List:
w = T*v
if w not in v_List and ht(w) < height:
w_New.append( w )
v_List += w_New
L = len( w_New )
print "%s new entr%s added..." % ( L, 'y was' if L == 1 else 'ies were' )
v_New = w_New[:]
print "A list with %s vectors was generated in %s steps" % ( len( v_List ), count )
return v_List
for height in ( 20, 50, 500 ):
print 60*'-'
print "Generation for height %s" % height
v_List = fillList( T_List, [ v, ], height )
Results:
------------------------------------------------------------
Generation for height 20
2 new entries were added...
5 new entries were added...
2 new entries were added...
0 new entries were added...
A list with 10 vectors was generated in 4 steps
------------------------------------------------------------
Generation for height 50
2 new entries were added...
8 new entries were added...
16 new entries were added...
7 new entries were added...
2 new entries were added...
1 new entry was added...
0 new entries were added...
A list with 37 vectors was generated in 7 steps
------------------------------------------------------------
Generation for height 500
2 new entries were added...
8 new entries were added...
32 new entries were added...
116 new entries were added...
232 new entries were added...
183 new entries were added...
85 new entries were added...
42 new entries were added...
21 new entries were added...
15 new entries were added...
10 new entries were added...
6 new entries were added...
5 new entries were added...
5 new entries were added...
5 new entries were added...
2 new entries were added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
0 new entries were added...
A list with 775 vectors was generated in 22 steps
sage:
As i said, possibly i am missing something... (Have to post and catch that train.)Tue, 07 Nov 2017 14:40:36 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?answer=39429#post-id-39429Comment by Daniel L for <p>My generating statistics differs, so i hope i understood the question well. Here is the quick code:</p>
<pre><code>T1 = matrix( ZZ, 4, [ -1,0,0,0, 2, 1,0,0, 4,0, 1,0, 4, 0,0, 1 ] )
T2 = matrix( ZZ, 4, [ 1,2,0,0, 0,-1,0,0, 0,4, 1,0, 0, 4,0, 1 ] )
T3 = matrix( ZZ, 4, [ 1,0,1,0, 0, 1,1,0, 0,0,-1,0, 0, 0,0, 1 ] )
T4 = matrix( ZZ, 4, [ 1,6,0,6, 0, 3,0,2, 0,4, 1,4, 0,-4,0,-3 ] )
T5 = matrix( ZZ, 4, [ 3,0,0,2, 6, 1,0,6, 4,0, 1,4, -4, 0,0,-3 ] )
T_List = ( T1, T2, T3, T4, T5 )
v = vector( ZZ, 4, [ 1,0,0,0 ] )
v = v.column()
def ht( w ):
return max( [ abs(entry) for entry in w ] )
def fillList( T_List, vector_List, height ):
v_List = vector_List[:] # and we will append
v_New = vector_List[:] # use them to generate new vectors, this is the "last wave"
count = 0 # give me some small control...
while v_New and count < 100 :
count += 1 # this will protect me against the usual programming errors
w_New = [] # and we will append, this is the "new wave"
for v in v_New:
for T in T_List:
w = T*v
if w not in v_List and ht(w) < height:
w_New.append( w )
v_List += w_New
L = len( w_New )
print "%s new entr%s added..." % ( L, 'y was' if L == 1 else 'ies were' )
v_New = w_New[:]
print "A list with %s vectors was generated in %s steps" % ( len( v_List ), count )
return v_List
for height in ( 20, 50, 500 ):
print 60*'-'
print "Generation for height %s" % height
v_List = fillList( T_List, [ v, ], height )
</code></pre>
<p>Results:</p>
<pre><code>------------------------------------------------------------
Generation for height 20
2 new entries were added...
5 new entries were added...
2 new entries were added...
0 new entries were added...
A list with 10 vectors was generated in 4 steps
------------------------------------------------------------
Generation for height 50
2 new entries were added...
8 new entries were added...
16 new entries were added...
7 new entries were added...
2 new entries were added...
1 new entry was added...
0 new entries were added...
A list with 37 vectors was generated in 7 steps
------------------------------------------------------------
Generation for height 500
2 new entries were added...
8 new entries were added...
32 new entries were added...
116 new entries were added...
232 new entries were added...
183 new entries were added...
85 new entries were added...
42 new entries were added...
21 new entries were added...
15 new entries were added...
10 new entries were added...
6 new entries were added...
5 new entries were added...
5 new entries were added...
5 new entries were added...
2 new entries were added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
1 new entry was added...
0 new entries were added...
A list with 775 vectors was generated in 22 steps
sage:
</code></pre>
<p>As i said, possibly i am missing something... (Have to post and catch that train.)</p>
http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39431#post-id-39431Dan: very nice code. I'm still working on checking it with what I have here, but it appears to agree with my hand calculation for vectors of ht < 20. Thank youTue, 07 Nov 2017 15:47:21 -0600http://ask.sagemath.org/question/39425/tree-of-vectors/?comment=39431#post-id-39431