Happy New Year 2024 ... and 2023's last teaser !

[J-F Garnier]

(01-03-2024 12:51 PM)Ajaja Wrote:  There are many rows and columns with zeros. I think, the fastest way to calculate permanent of the matrix is to sort it first, then transpose, sort again and after that use J-F Garnier optimized subprogram.

If you look closely at my solution, you will see that I sorted the array rows by the number of 1 in each row, not by the value of the binary representation:

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 0,0,1,1,0,0,0,0,0,1,0,1
23 DATA 0,0,1,1,0,0,0,0,0,1,1,1
24 DATA 1,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,1,0,1,1,1
26 DATA 1,0,1,1,1,0,0,1,0,1,1,1
27 DATA 0,1,0,1,1,1,1,1,1,1,0,1
28 DATA 1,0,1,1,1,0,1,1,0,1,1,1
29 DATA 1,0,1,1,1,0,1,1,1,1,1,1
30 DATA 1,0,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

This was the most important part of my 'optimization'. The other one was to consequently skip the minor calculation for the zero elements:

135 IF A(1,K)=0 THEN 145 ! little optimization

In that way, the recursive tree was reduced to 2 paths at each level instead of 11 (up to row 8), mostly important for the first recursive steps to cut calculation time.
I did notice the structure of the sorted array and the exception of row 8 (of the sorted array), but without paying too much attention to it.
I was quite happy to get a solution in HP BASIC in a sensible time, even on a machine as slow as the 71B.

Of course, as Valentin pointed out, this solution is only effective for this case with this special array structure.

J-F