ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 09 Jan 2013 07:24:11 -0600Recursive backtracking function: how to clear variables on new function call?https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/I've been trying to write a simple function to make lists of all the Young diagrams/partitions between a starting partition ('top') and an ending partition ('bot'), with each step in the list a covering relation (exactly one box difference in each step).
For instance, I would like to input [2,1] for top and [1] for bot and get
[[2,1],[2],[1]]
[[2,1],[1,1],[1]]
as my outputs. (I want to do this because it's useful for some computations with Littlewood-Richardson coefficients; having the lists that give each partition in a path between top and bot will be useful for other computations.)
My code at present has an echo, and worse, I can't figure out where to initialize path_list. Where do I put path_list = [] -- or create other lists -- to make sure that:
1. I get a separate list for each path, and
2. Calling the function again clears path_list?
(2) is worst: right now, since path_list is an internally-defined variable, I get the following bad behavior:
sage: load "makepartitionlist.sage"
sage: get_path([1],[1])
[[1]]
[[1]]
sage: get_path([1],[1])
[[1], [1]]
[[1], [1]]
sage: get_path([1],[1])
[[1], [1], [1]]
[[1], [1], [1]]
because path_list is not cleared when I call get_path again (which I'd hoped putting path_list = [] in the arguments would accomplish).
The code:
def get_path(top, bot, path_list = []):
path_list.append(top)
if top == bot:
print path_list
return path_list
if not Partition(top).contains(Partition(bot)):
return None
for i in range(0,len(Partition(top).down_list())):
p = Partition(top).down_list()[i]
if Partition(p).contains(bot):
path_list.append(p)
get_path(p, bot, path_list)
I'm using Sage 5.0.1 with Sage-combinat providing the Partition function and others.Fri, 04 Jan 2013 11:50:38 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/Answer by Bétréma for <p>I've been trying to write a simple function to make lists of all the Young diagrams/partitions between a starting partition ('top') and an ending partition ('bot'), with each step in the list a covering relation (exactly one box difference in each step). </p>
<p>For instance, I would like to input [2,1] for top and [1] for bot and get </p>
<p>[[2,1],[2],[1]]</p>
<p>[[2,1],[1,1],[1]] </p>
<p>as my outputs. (I want to do this because it's useful for some computations with Littlewood-Richardson coefficients; having the lists that give each partition in a path between top and bot will be useful for other computations.)</p>
<p>My code at present has an echo, and worse, I can't figure out where to initialize path_list. Where do I put path_list = [] -- or create other lists -- to make sure that:</p>
<ol>
<li>I get a separate list for each path, and</li>
<li>Calling the function again clears path_list? </li>
</ol>
<p>(2) is worst: right now, since path_list is an internally-defined variable, I get the following bad behavior:</p>
<p>sage: load "makepartitionlist.sage"</p>
<p>sage: get_path([1],[1])</p>
<p>[[1]]</p>
<p>[[1]]</p>
<p>sage: get_path([1],[1])</p>
<p>[[1], [1]]</p>
<p>[[1], [1]]</p>
<p>sage: get_path([1],[1])</p>
<p>[[1], [1], [1]]</p>
<p>[[1], [1], [1]]</p>
<p>because path_list is not cleared when I call get_path again (which I'd hoped putting path_list = [] in the arguments would accomplish).</p>
<p>The code:</p>
<pre><code>def get_path(top, bot, path_list = []):
path_list.append(top)
if top == bot:
print path_list
return path_list
if not Partition(top).contains(Partition(bot)):
return None
for i in range(0,len(Partition(top).down_list())):
p = Partition(top).down_list()[i]
if Partition(p).contains(bot):
path_list.append(p)
get_path(p, bot, path_list)
</code></pre>
<p>I'm using Sage 5.0.1 with Sage-combinat providing the Partition function and others.</p>
https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?answer=14431#post-id-14431I think the following code gives the good output (but is far from optimal, many computations are repeated again and again, as in the naive recursive computation of the Fibonacci sequence), here parameters are assumed to be partitions:
def get_paths(top, bot):
if top == bot:
return [[top]]
path_list = []
for p in top.down_list():
if p.contains(bot):
path_list += get_paths(p, bot)
for u in path_list:
u.append(top)
return path_list
For example:
sage: gp = get_paths (Partition([3,3,1]),Partition([2,1])); len(gp)
8
sage: len (get_paths (Partition([3,3,2]),Partition([1])))
42
Actually we are computing functions already defined in Sage:
sage: sst = StandardSkewTableaux([[3, 3, 1], [2, 1]])
sage: sst.cardinality()
8
sage: StandardTableaux([3,3,2]).cardinality()
42
Use <code>sst.list()</code> to get the "same" list as the one computed by <code>get_paths()</code>. You may eventually look at the source code of these functions, in the modules <tt>sage.combinat.tableau</tt> and <tt>sage.combinat.skew_tableau</tt> .
Amitiés.
Sat, 05 Jan 2013 09:52:12 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?answer=14431#post-id-14431Comment by kaisat for <p>I think the following code gives the good output (but is far from optimal, many computations are repeated again and again, as in the naive recursive computation of the Fibonacci sequence), here parameters are assumed to be partitions:</p>
<pre><code>def get_paths(top, bot):
if top == bot:
return [[top]]
path_list = []
for p in top.down_list():
if p.contains(bot):
path_list += get_paths(p, bot)
for u in path_list:
u.append(top)
return path_list
</code></pre>
<p>For example:</p>
<pre><code>sage: gp = get_paths (Partition([3,3,1]),Partition([2,1])); len(gp)
8
sage: len (get_paths (Partition([3,3,2]),Partition([1])))
42
</code></pre>
<p>Actually we are computing functions already defined in Sage:</p>
<pre><code>sage: sst = StandardSkewTableaux([[3, 3, 1], [2, 1]])
sage: sst.cardinality()
8
sage: StandardTableaux([3,3,2]).cardinality()
42
</code></pre>
<p>Use <code>sst.list()</code> to get the "same" list as the one computed by <code>get_paths()</code>. You may eventually look at the source code of these functions, in the modules <tt>sage.combinat.tableau</tt> and <tt>sage.combinat.skew_tableau</tt> .</p>
<p>Amitiés.</p>
https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18419#post-id-18419Wonderful, and many thanks! I am testing this and your code above seems to do exactly what I'd like. It seems that += rather than append is the way to go -- a key improvement -- and I will think about exactly how the placement of path_list = [] helped as well.Tue, 08 Jan 2013 14:47:44 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18419#post-id-18419Comment by Bétréma for <p>I think the following code gives the good output (but is far from optimal, many computations are repeated again and again, as in the naive recursive computation of the Fibonacci sequence), here parameters are assumed to be partitions:</p>
<pre><code>def get_paths(top, bot):
if top == bot:
return [[top]]
path_list = []
for p in top.down_list():
if p.contains(bot):
path_list += get_paths(p, bot)
for u in path_list:
u.append(top)
return path_list
</code></pre>
<p>For example:</p>
<pre><code>sage: gp = get_paths (Partition([3,3,1]),Partition([2,1])); len(gp)
8
sage: len (get_paths (Partition([3,3,2]),Partition([1])))
42
</code></pre>
<p>Actually we are computing functions already defined in Sage:</p>
<pre><code>sage: sst = StandardSkewTableaux([[3, 3, 1], [2, 1]])
sage: sst.cardinality()
8
sage: StandardTableaux([3,3,2]).cardinality()
42
</code></pre>
<p>Use <code>sst.list()</code> to get the "same" list as the one computed by <code>get_paths()</code>. You may eventually look at the source code of these functions, in the modules <tt>sage.combinat.tableau</tt> and <tt>sage.combinat.skew_tableau</tt> .</p>
<p>Amitiés.</p>
https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18416#post-id-18416Look at the first path returned by get_paths in my example: [[2, 1], [2, 1, 1], [2, 2, 1], [3, 2, 1], [3, 3, 1]], it's coded by the last skew tableau returned by sst.list(): [[None, None, 3], [None, 2, 4], [1]], because we add the first cell in a third new row, the second one is appended to the second row, the third one to the first row, and the fourth one to the second row (again). Anybody familiar with the subject may explain you the correspondence, it's easier on a sheet of paper or on a blackboard :-)Wed, 09 Jan 2013 07:24:11 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18416#post-id-18416Comment by kaisat for <p>I think the following code gives the good output (but is far from optimal, many computations are repeated again and again, as in the naive recursive computation of the Fibonacci sequence), here parameters are assumed to be partitions:</p>
<pre><code>def get_paths(top, bot):
if top == bot:
return [[top]]
path_list = []
for p in top.down_list():
if p.contains(bot):
path_list += get_paths(p, bot)
for u in path_list:
u.append(top)
return path_list
</code></pre>
<p>For example:</p>
<pre><code>sage: gp = get_paths (Partition([3,3,1]),Partition([2,1])); len(gp)
8
sage: len (get_paths (Partition([3,3,2]),Partition([1])))
42
</code></pre>
<p>Actually we are computing functions already defined in Sage:</p>
<pre><code>sage: sst = StandardSkewTableaux([[3, 3, 1], [2, 1]])
sage: sst.cardinality()
8
sage: StandardTableaux([3,3,2]).cardinality()
42
</code></pre>
<p>Use <code>sst.list()</code> to get the "same" list as the one computed by <code>get_paths()</code>. You may eventually look at the source code of these functions, in the modules <tt>sage.combinat.tableau</tt> and <tt>sage.combinat.skew_tableau</tt> .</p>
<p>Amitiés.</p>
https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18418#post-id-18418I am not getting the same result with sst.list() though, so will look at that. It did occur to me that the tableau packages might be able to help but I could not quite see what to do.Tue, 08 Jan 2013 14:48:38 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?comment=18418#post-id-18418Answer by Bétréma for <p>I've been trying to write a simple function to make lists of all the Young diagrams/partitions between a starting partition ('top') and an ending partition ('bot'), with each step in the list a covering relation (exactly one box difference in each step). </p>
<p>For instance, I would like to input [2,1] for top and [1] for bot and get </p>
<p>[[2,1],[2],[1]]</p>
<p>[[2,1],[1,1],[1]] </p>
<p>as my outputs. (I want to do this because it's useful for some computations with Littlewood-Richardson coefficients; having the lists that give each partition in a path between top and bot will be useful for other computations.)</p>
<p>My code at present has an echo, and worse, I can't figure out where to initialize path_list. Where do I put path_list = [] -- or create other lists -- to make sure that:</p>
<ol>
<li>I get a separate list for each path, and</li>
<li>Calling the function again clears path_list? </li>
</ol>
<p>(2) is worst: right now, since path_list is an internally-defined variable, I get the following bad behavior:</p>
<p>sage: load "makepartitionlist.sage"</p>
<p>sage: get_path([1],[1])</p>
<p>[[1]]</p>
<p>[[1]]</p>
<p>sage: get_path([1],[1])</p>
<p>[[1], [1]]</p>
<p>[[1], [1]]</p>
<p>sage: get_path([1],[1])</p>
<p>[[1], [1], [1]]</p>
<p>[[1], [1], [1]]</p>
<p>because path_list is not cleared when I call get_path again (which I'd hoped putting path_list = [] in the arguments would accomplish).</p>
<p>The code:</p>
<pre><code>def get_path(top, bot, path_list = []):
path_list.append(top)
if top == bot:
print path_list
return path_list
if not Partition(top).contains(Partition(bot)):
return None
for i in range(0,len(Partition(top).down_list())):
p = Partition(top).down_list()[i]
if Partition(p).contains(bot):
path_list.append(p)
get_path(p, bot, path_list)
</code></pre>
<p>I'm using Sage 5.0.1 with Sage-combinat providing the Partition function and others.</p>
https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?answer=14430#post-id-14430This is a very partial answer, but in a Python crash course (by William Stein I presume, now I can't find the link) I learned this example:
def f(a, L=[]):
L.append(a)
return L
with the following astonishing successive outputs:
sage: f(2)
[2]
sage: f(5)
[2, 5]
sage: f(4)
[2, 5, 4]
(this is pure Python, Sage is not guilty).Sat, 05 Jan 2013 07:35:58 -0600https://ask.sagemath.org/question/9688/recursive-backtracking-function-how-to-clear-variables-on-new-function-call/?answer=14430#post-id-14430