[Edu-sig] Re: Determinants and permutations

[Daniel Ajoy]

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