Author 
Message 
Mark Lawton science forum beginner
Joined: 22 Mar 2006
Posts: 11

Posted: Wed Mar 22, 2006 10:57 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



Richard J. Fateman wrote:
Quote:  An equivalent, but perhaps more stylish program for your
color problem, which shows that "protection under recursion"
that you thought you needed, you did not need at all.
You also did not need to copy anything, and there was
a potential bug in that you were changing a global variable
named count. I do not know if the program can be made
smaller, but computing with lists, permutations, etc is
very natural in languages like lisp. That's why I used
"cons" in there..
I would expect this program to be much faster than the
other one, though it probably doesn't matter much.
RJF

Excellent!!!
It does indeed run about 20% faster (based on a sample size of 1 )
 but more importantly, it can go much deeper. My original program (as
modified by Mark) would fall over at approximately taking 12 from 80
with a "bind stack overflow" error. With your modifications, I have
been unable to find an upper limit  even if it takes 10 minutes to run
to completion!
Thankyou very much (and to Mark as well) for this valuable education in
Maxima programming. 

Back to top 


Richard J. Fateman science forum addict
Joined: 04 May 2005
Posts: 81

Posted: Wed Mar 22, 2006 8:42 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



An equivalent, but perhaps more stylish program for your
color problem, which shows that "protection under recursion"
that you thought you needed, you did not need at all.
You also did not need to copy anything, and there was
a potential bug in that you were changing a global variable
named count. I do not know if the program can be made
smaller, but computing with lists, permutations, etc is
very natural in languages like lisp. That's why I used
"cons" in there..
I would expect this program to be much faster than the
other one, though it probably doesn't matter much.
RJF
reduceColor(fullList,take) := cons(min(fullList[1],take)  1,
rest(fullList))$
colors(list, take, taken, startTake) :=
if list[1] < 0 then 0
else
if length(list) = 2 then
if take < 0 then 0
else
if take = 0 then 1
else
if list[1] + list[2] < take then 0
else
if list[1] + list[2] = take then 1
else
block([count: 0],
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
count)
else
block([ntake: min(take,list[1])],
colors(rest(list), startTake  ntake  taken, taken +ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))$ 

Back to top 


Seeker of Truth science forum beginner
Joined: 11 Oct 2005
Posts: 33

Posted: Wed Mar 22, 2006 7:51 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



Mark Lawton wrote:
Quote:  Hi MFFAI,
I've got it working for you now!

Thanks very much Mark  that was a sharp piece of debugging!
It's working exactly as I intended now, and producing correct results.
For example:
If I have 4 blue, 3 red, 2 green, and 1 yellow marbles, how many
combinations of colours can I make with any 4 of them?
(%i3) colors([4,3,2,1],4,0,4);
(%o3) 20
If I have 6 white, 5 black, 4 blue, 3 red, 2 green, and 1 yellow
marbles, how many combinations of colours can I make with any 6 of
them?
(%i4) colors([6,5,4,3,2,1],6,0,6);
(%o4) 259
As I said before, such problems, while simple to express, defy simple
combinatorical solution! 

Back to top 


Mark Lawton science forum beginner
Joined: 22 Mar 2006
Posts: 11

Posted: Wed Mar 22, 2006 3:35 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



Hi MFFAI,
I've got it working for you now!
reduceColor(fullList,take) := (newList: copylist(fullList), newList[1]:
min(fullList[1],take)  1, newList);
colors(qlist, qtake, qtaken, startTake) :=
block([list: qlist, take: qtake, taken: qtaken, ntake],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(ntake: min(take,list[1]),
return(colors(rest(list), startTake  ntake  taken, taken +
ntake,startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
I made the following changes:
1. erroneous "listcopy" removed (as previously stated)
2. variable "ntake" added to list of protected variables at start of
block command
3. I replaced your if..then..else statement to select the smaller of
take and list[1] with min(take,list[1]) (no difference to program 
just looks more elegant )
It's a nice program  I'll be adding it to my archive!
Maths For Fun And Insight wrote:
Quote:  If I do a simple factorial recursion, there is no problem whatsoever:
(%i6) facty(x) := if x=1 then 1 else x*facty(x1);
(%o6) facty(x) := if x = 1 then 1 else x facty(x  1)
(%i7) facty(5);
(%o7) 120
However  I wrote a program to try to quickly answer the following
question (which defies simple combinatorical solution): if I have a
list of numbers of marbles of different colours, how many different
combinations of colours can I make with n of those marbles? (e.g. if I
have 3 reds, 2 greens and 1 yellow, I can make 6 different combinations
of 3 balls  red red red, red red green, red red yellow, red green
green, red green yellow, green green yellow). This program gives
incorrect results  and the reason is that Maxima is not protecting the
variables under recursion:
reduceColor(fullList,take) := (newList: copylist(fullList), newList[1]:
min(fullList[1],take)  1, newList);
colors(list, take, taken, startTake) :=
block([],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
(%i trace(colors);
(%o [colors]
(%i9) colors([4,3,2,1],4,0,4);
1 Enter colors [[4, 3, 2, 1], 4, 0, 4]
2 Enter colors [[3, 2, 1], 0, 4, 4]
3 Enter colors [[2, 1], 0, 4, 4]
3 Exit colors 1
3 Enter colors [[ 1, 2, 1], 0, 4, 4]
3 Exit colors 0
2 Exit colors 1
2 Enter colors [[ 1, 3, 2, 1], 0, 0, 4]
2 Exit colors 0
1 Exit colors 1
Reading the part of the manual that refers to functions (
http://maxima.sourceforge.net/docs/manual/en/maxima_40.html#SEC152 ),
it is supposed to be possible to protect variables by putting their
names in the list at the start of the block. However  if I do
something like this:
colors(qlist, qtake, qtaken, startTake) :=
block([list: listcopy(qlist), take: qtake, taken: qtaken],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
I get the following error:
(%i9) colors([3,2,1],4,0,4);
Maxima was unable to evaluate the predicate:
errexp1
#0: colors(qlist=[3,2,1],qtake=4,qtaken=0,starttake=4)
 an error. Quitting. To debug this try debugmode(true);
Can anyone offer any advice, please? 


Back to top 


Richard Fateman science forum Guru Wannabe
Joined: 03 May 2005
Posts: 181

Posted: Wed Mar 22, 2006 3:18 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



"Mark Lawton" <creamrisestothetop@gmail.com> wrote in message >
Quote:  In the above line, you wrote listcopy instead of copylist (list: qlist
seems to work just as well anyway). That removes the error.
It is still giving the wrong answer for colors([4,3,2,1]4,0,4)  but
that might be due to a programming error  I will study it a bit
more...

You don't need list:qlist either. Just rename the parameter to list.
Since you are not doing any assignments to list, you don't need
a local copy of it.
Also instead of writing
if A then return(B) else return(C) ....
you might consider
return( if A then B else C)
or if the program control flow allows it, and you
are at the end of the program, just
if A then B else C.
Of course it may still have a bug!
RJF 

Back to top 


Mark Lawton science forum beginner
Joined: 22 Mar 2006
Posts: 11

Posted: Wed Mar 22, 2006 2:36 pm Post subject:
Re: Can Maxima Protect Variables Under Recursion?



Maths For Fun And Insight wrote:
Quote:  If I do a simple factorial recursion, there is no problem whatsoever:
(%i6) facty(x) := if x=1 then 1 else x*facty(x1);
(%o6) facty(x) := if x = 1 then 1 else x facty(x  1)
(%i7) facty(5);
(%o7) 120
However  I wrote a program to try to quickly answer the following
question (which defies simple combinatorical solution): if I have a
list of numbers of marbles of different colours, how many different
combinations of colours can I make with n of those marbles? (e.g. if I
have 3 reds, 2 greens and 1 yellow, I can make 6 different combinations
of 3 balls  red red red, red red green, red red yellow, red green
green, red green yellow, green green yellow). This program gives
incorrect results  and the reason is that Maxima is not protecting the
variables under recursion:
reduceColor(fullList,take) := (newList: copylist(fullList), newList[1]:
min(fullList[1],take)  1, newList);
colors(list, take, taken, startTake) :=
block([],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
(%i trace(colors);
(%o [colors]
(%i9) colors([4,3,2,1],4,0,4);
1 Enter colors [[4, 3, 2, 1], 4, 0, 4]
2 Enter colors [[3, 2, 1], 0, 4, 4]
3 Enter colors [[2, 1], 0, 4, 4]
3 Exit colors 1
3 Enter colors [[ 1, 2, 1], 0, 4, 4]
3 Exit colors 0
2 Exit colors 1
2 Enter colors [[ 1, 3, 2, 1], 0, 0, 4]
2 Exit colors 0
1 Exit colors 1
Reading the part of the manual that refers to functions (
http://maxima.sourceforge.net/docs/manual/en/maxima_40.html#SEC152 ),
it is supposed to be possible to protect variables by putting their
names in the list at the start of the block. However  if I do
something like this:
colors(qlist, qtake, qtaken, startTake) :=
block([list: listcopy(qlist), take: qtake, taken: qtaken],

In the above line, you wrote listcopy instead of copylist (list: qlist
seems to work just as well anyway). That removes the error.
It is still giving the wrong answer for colors([4,3,2,1]4,0,4)  but
that might be due to a programming error  I will study it a bit
more...
Quote:  if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
I get the following error:
(%i9) colors([3,2,1],4,0,4);
Maxima was unable to evaluate the predicate:
errexp1
#0: colors(qlist=[3,2,1],qtake=4,qtaken=0,starttake=4)
 an error. Quitting. To debug this try debugmode(true);
Can anyone offer any advice, please? 


Back to top 


Seeker of Truth science forum beginner
Joined: 11 Oct 2005
Posts: 33

Posted: Wed Mar 22, 2006 9:23 am Post subject:
Can Maxima Protect Variables Under Recursion?



If I do a simple factorial recursion, there is no problem whatsoever:
(%i6) facty(x) := if x=1 then 1 else x*facty(x1);
(%o6) facty(x) := if x = 1 then 1 else x facty(x  1)
(%i7) facty(5);
(%o7) 120
However  I wrote a program to try to quickly answer the following
question (which defies simple combinatorical solution): if I have a
list of numbers of marbles of different colours, how many different
combinations of colours can I make with n of those marbles? (e.g. if I
have 3 reds, 2 greens and 1 yellow, I can make 6 different combinations
of 3 balls  red red red, red red green, red red yellow, red green
green, red green yellow, green green yellow). This program gives
incorrect results  and the reason is that Maxima is not protecting the
variables under recursion:
reduceColor(fullList,take) := (newList: copylist(fullList), newList[1]:
min(fullList[1],take)  1, newList);
colors(list, take, taken, startTake) :=
block([],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
(%i trace(colors);
(%o [colors]
(%i9) colors([4,3,2,1],4,0,4);
1 Enter colors [[4, 3, 2, 1], 4, 0, 4]
2 Enter colors [[3, 2, 1], 0, 4, 4]
3 Enter colors [[2, 1], 0, 4, 4]
3 Exit colors 1
3 Enter colors [[ 1, 2, 1], 0, 4, 4]
3 Exit colors 0
2 Exit colors 1
2 Enter colors [[ 1, 3, 2, 1], 0, 0, 4]
2 Exit colors 0
1 Exit colors 1
Reading the part of the manual that refers to functions (
http://maxima.sourceforge.net/docs/manual/en/maxima_40.html#SEC152 ),
it is supposed to be possible to protect variables by putting their
names in the list at the start of the block. However  if I do
something like this:
colors(qlist, qtake, qtaken, startTake) :=
block([list: listcopy(qlist), take: qtake, taken: qtaken],
if list[1] < 0 then
return(0)
else
if length(list) = 2 then
if take < 0 then
return(0)
else
if take = 0 then
return(1)
else
if list[1] + list[2] < take then
return(0)
else
if list[1] + list[2] = take then
return(1)
else
(count: 0,
for i: 0 thru list[1] do
for j: 0 thru list[2] do
if i + j = take then
count: count + 1,
return(count))
else
(if take > list[1] then
ntake: list[1]
else
ntake: take,
return(colors(rest(list), startTake  ntake  taken, taken + ntake,
startTake)
+ colors(reduceColor(list,ntake), ntake, taken, startTake))))$
I get the following error:
(%i9) colors([3,2,1],4,0,4);
Maxima was unable to evaluate the predicate:
errexp1
#0: colors(qlist=[3,2,1],qtake=4,qtaken=0,starttake=4)
 an error. Quitting. To debug this try debugmode(true);
Can anyone offer any advice, please? 

Back to top 


Google


Back to top 



The time now is Thu Feb 21, 2019 8:25 am  All times are GMT

