FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Symbolic
Can Maxima Protect Variables Under Recursion?
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
Author Message
Mark Lawton
science forum beginner


Joined: 22 Mar 2006
Posts: 11

PostPosted: Wed Mar 22, 2006 10:57 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with quote

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 Smile )
- 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

PostPosted: Wed Mar 22, 2006 8:42 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with 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



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

PostPosted: Wed Mar 22, 2006 7:51 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with quote

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

PostPosted: Wed Mar 22, 2006 3:35 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with quote

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 Wink )

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(x-1);
(%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))))$

(%iCool trace(colors);
(%oCool [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

PostPosted: Wed Mar 22, 2006 3:18 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with quote

"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

PostPosted: Wed Mar 22, 2006 2:36 pm    Post subject: Re: Can Maxima Protect Variables Under Recursion? Reply with quote

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(x-1);
(%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))))$

(%iCool trace(colors);
(%oCool [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

PostPosted: Wed Mar 22, 2006 9:23 am    Post subject: Can Maxima Protect Variables Under Recursion? Reply with quote

If I do a simple factorial recursion, there is no problem whatsoever:

(%i6) facty(x) := if x=1 then 1 else x*facty(x-1);
(%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))))$

(%iCool trace(colors);
(%oCool [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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
The time now is Thu Feb 21, 2019 8:25 am | All times are GMT
Forum index » Science and Technology » Math » Symbolic
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts maxima again... jimmij Symbolic 3 Wed Jul 19, 2006 5:28 pm
No new posts maxima problem jimmij Symbolic 2 Mon Jul 17, 2006 11:55 am
No new posts Apparent Bug In "Permutations" Function In Maxima 5.9.3 Mark Lawton Symbolic 2 Sat Jul 15, 2006 11:31 am
No new posts Is sum of two normally distributed variables normally dis... Konrad Viltersten Probability 2 Mon Jul 10, 2006 5:17 am
No new posts HOW AMERICANS should PROTECT themselves from EVIL FBI, CI... McGinnn Math 2 Sun Jul 09, 2006 9:36 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0187s ][ Queries: 20 (0.0025s) ][ GZIP on - Debug on ]