On 9 May 01, at 12:01, edu-sig-request@python.org wrote:
Now to turn all of that into code. Now I know how I'm teaching recursion this summer.
However, if you want to be brute force about it, and non-recursive, you just need the n! permutations of column elements, picking one element from each column as you go down the rows. Each selection nets you a product, and you still need to compute its sign (talked about that just a post or two back).
I was relieved to find this, as I was looking at the selective (row,column) blocking with recursion, and not liking the looks of that challenge.
I did, sometime ago, programmed the recursive definition of determinant using adjoints and minors, I did it in Logo (MSWLogo to be precise), but it was terribly slow. That is really "brute force" approach. I thank Kirby for showing me the permutations approach. Now, that with his help I was able to figure out the pattern in the signs, my determinant implementation in Logo works wonderfully (I tested with a 6x6 matrix).
How do I get the permutations? Well, I'm sure there's lots of ways, but I just set up a base-4 number (for a 4x4 matrix) and count from 0000, 0001, 0002 -- except I eliminate any string with repeating digits, so 0123 is the first admitted. Add 1 to that, base 4, and you get 0130, which isn't "legal" either, but you get the idea (add up through 3210, crossing out any with repeating digits, and you've got your 4!=24 legal permutations). I could refine this some (i.e. start with 0123..(n-1) -- but it works well enough for my purposes as is, so further optimizing is back burner for now.
That is the advantage of an object oriented languaje: a lot of the code can be reused easily. I developed my permutations algorithm using the backtracking approach, and its more general. Since I had that algorithm ready, it was fairly easy to develop the determinant algorithm too. My permutations algorithm is called permconj since "conjunto" is "set" in spanish. show permconj [1 [a b c]] [[a] [b] [c]] show permconj [2 [a b c]] [[a b] [a c] [b c] [b a] [c a] [c b]] show permconj [3 [a b c]] [[a b c] [a c b] [b c a] [b a c] [c a b] [c b a]] show permconj [0 [a b c]] [[]] show count [a b c] 3 show count permconj [6 [a b c d e f]] 720 I also have "permu" that returns only the counts. es permu [3 1] 3 es permu [3 0] 1 es permu [3 2] 6 es permu [3 3] 6 Anyway, one of these days I'm going to tray to do Kirbys polyhedra in MSWLogo too, since MSWLogo has 3D graphic rendition incorporated. Daniel