Search   Memberlist   Usergroups
 Page 1 of 1 [3 Posts]
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))))\$
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

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 two-sports", soln[2] + soln[4] +
soln[6])\$

The output confirmed that there was always a total of 15 people doing 2
sports.
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 in-place. I've committed a 1-line 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 (copy-list (cdr a)) '\$orderlessp)))
(t
(setq a (require-set 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.
foobar(bazquux(mumble(x))) write foobar (bazquux (mumble (x)))
(put a space between function name and parenthesis).

FWIW, YMMV, HTH.

Robert Dodier

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [3 Posts]
 The time now is Fri Sep 21, 2018 9:28 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Generating function for Mathieu functions cosmicstring@gmail.com Math 1 Fri Jul 21, 2006 8:39 am Choice function over finite sets Peter Webb Math 5 Fri Jul 21, 2006 3:28 am Function from Taylor series? Nathan Urban Research 1 Thu Jul 20, 2006 12:48 am Function not in L_1 {[0,1]}, but satisfies ...? atkrunner@hotmail.com Math 12 Thu Jul 20, 2006 12:46 am maxima again... jimmij Symbolic 3 Wed Jul 19, 2006 5:28 pm