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

Posted: Sat Jul 15, 2006 11:31 am Post subject:
Apparent Bug In "Permutations" Function In Maxima 5.9.3



I was investigating the following question: "In my class, there are 99
students other than me. 50 of us play soccer, 45 basketball and 50 play
volleyball. Only 15 of us play all three games. Everyone plays at least
one game. How many play only two games?"
I wrote a Maxima program, but its output was the error message, "part
fell off end".
A bit of debugging yielded the fact that the "permutations" function is
altering variables that it shouldn't. Closing and restarting Maxima
makes no difference.
In the code, the following 2 lines have been added for debugging:
if length(part(soccer,1)) = 2 then print(1)
if length(part(soccer,1)) = 2 then print(2)
The fact that when the code runs, 2 is printed before 1 seems to show
that the statement socPerm: permutations(soccerSet) is illegally
altering the value of the variable "soccer".
Here is the code:
(soccer: integer_partitions(35,3),
baseball: integer_partitions(35,3),
volleyball: integer_partitions(30,3),
listintersect(list1, list2) := intersect(setify(list1), setify(list2)),
for soccerSet in soccer do
for baseSet in baseball do
if cardinality(listintersect(soccerSet, baseSet)) > 0 then
for volleySet in volleyball do
if cardinality(listintersect(soccerSet, volleySet)) > 0 and
cardinality(listintersect(baseSet, volleySet)) > 0 then
(if length(part(soccer,1)) = 2 then print(1),
socPerm: permutations(soccerSet),
if length(part(soccer,1)) = 2 then print(2),
basPerm: permutations(baseSet),
volPerm: permutations(volleySet),
for socSoln in socPerm do
for basSoln in basPerm do
if part(socSoln,1) = part(basSoln,1) then
for volSoln in volPerm do
if part(socSoln,2) = part(volSoln,1) and part(volSoln,2) =
part(basSoln,2) then
(soc: part(socSoln,3),
socBas: part(socSoln,1),
socVol: part(socSoln,3),
bas: part(basSoln, 3),
basVol: part(basSoln,2),
vol: part(volSoln,3),
twoGames: socBas + socVol + basVol,
print("Soc",soc,", bas",bas,", vol",vol,",
soc&bas",socBas,", soc&vol",socVol,", bas&vol",basVol,", two
games",twoGames))))$ 

Back to top 


GLaight@googlemail.com science forum beginner
Joined: 15 Jul 2006
Posts: 1

Posted: Sat Jul 15, 2006 3:49 pm Post subject:
Re: Apparent Bug In "Permutations" Function In Maxima 5.9.3



Off topic to the apparent bug  but I ran a different program and found
the solution (warning  this took over 2 hours to run on my PC):
(solns: set(),
test: integer_partitions(100,7),
for lists in test do
if member(15, lists) then
(perms: permutations(lists),
for sector in perms do
if part(sector, 5) = 15 then
(soc: part(sector,1) + part(sector,2) + part(sector,4) + 15,
bas: part(sector,2) + part(sector,3) + part(sector,6) + 15,
vol: part(sector,4) + part(sector,6) + part(sector,7) + 15,
if soc = 50 and bas = 50 and vol = 45 then
solns: adjoin(sector, solns))))$
After running this, the cardinality of the "solns" solution set was 136
 so I ran another program:
for soln in solns do
print("Soc",soln[1],", Bas",soln[3],", Vol",soln[7],",
soc+Bas",soln[2],", soc+Vol",
soln[4],", Bas+Vol",soln[6],", Total twosports", soln[2] + soln[4] +
soln[6])$
The output confirmed that there was always a total of 15 people doing 2
sports. 

Back to top 


robert.dodier@gmail.com science forum beginner
Joined: 02 Oct 2005
Posts: 26

Posted: Sun Jul 16, 2006 6:37 pm Post subject:
Re: Apparent Bug In "Permutations" Function In Maxima 5.9.3



Mark Lawton wrote:
Quote:  A bit of debugging yielded the fact that the "permutations" function is
altering variables that it shouldn't.

Thanks for reporting this bug. The problem is that the Lisp SORT
function modifies its argument inplace. I've committed a 1line patch
to Maxima cvs to copy the argument before sorting in permutations.
Here is the patch  you can fix your copy of maxima/src/nset.lisp by
hand if you wish.
 nset.lisp 3 Jul 2006 18:47:45 0000 1.11
+++ nset.lisp 16 Jul 2006 18:13:17 0000
@@ 333,7 +333,7 @@
(defun $permutations (a)
(cond (($listp a)
 (setq a (sort (cdr a) '$orderlessp)))
+ (setq a (sort (copylist (cdr a)) '$orderlessp)))
(t
(setq a (requireset a "$permutations"))))
Quote:  bas: part(basSoln, 3),
basVol: part(basSoln,2),
vol: part(volSoln,3),
twoGames: socBas + socVol + basVol,
print("Soc",soc,", bas",bas,", vol",vol,",
soc&bas",socBas,", soc&vol",socVol,", bas&vol",basVol,", two
games",twoGames))))$

You didn't ask for my advice but here it is all the same.
(1) I don't recommend calling part in general. Maybe foo[1],
foo[2] etc works OK here.
(2) Instead of printing all the partial results, construct a list
to hold the results. This obviates printing in the loop (which
might take an appreciable fraction of the run time) and also
makes the results available for inspection afterwards.
(3) I find code with some whitespace in it easier to read.
E.g. instead of fooBar write foo_bar, and instead of
foobar(bazquux(mumble(x))) write foobar (bazquux (mumble (x)))
(put a space between function name and parenthesis).
FWIW, YMMV, HTH.
Robert Dodier 

Back to top 


Google


Back to top 



The time now is Wed Apr 25, 2018 6:57 am  All times are GMT

