Applications of the monad f/ .g are easier to
envision in an alternative formulation of the
generalized determinant, namely as f/ over g/
over diagonals of matrices obtained by all
possible permutations of the major cells.
(Think of the ordinary determinant. Many texts
have the formula:
sigma (sign p) * A[1;p1] * A[2;p2] * ... * A[n;pn]
p
Where the sum is over all permutations p .)
In SATN-42, Iverson described the use of the
genealized determinant in "assignment problems"
thus: (I translated the expressions from SHARP APL
to J):
One of n machines is assigned to each one of n
tasks in some optimal way, the cost associated
with assigning machine i to task j being given by
element (<i,j){m of the square matrix m .
If we wish to minimize the sum of the costs in
the assignment, then the optimum value is given
by <./ .+ m, since the summation (+/) is applied
to each of the !#m possible assignments, and the
minimum (<./) is applied over them. Other useful
function pairs in assignment type problems include
>.+ <.* >.* <.>. >.<.
Some uses of the generlized determinant described
by SATN-42 are:
+./ . *. if y covers a Latin Square
+ / . *. how many Latin Squares are covered
<./ . + assignment problem
>./ . + assignment problem
<./ . * assignment problem
>./ . * assignment problem
<./ . >. assignment problem
>./ . <. assignment problem
I have thought of entering SATN-42 into the J Wiki,
but the difficulties for a modern reader would be
formidable. There is the translation from APL to J,
and the SATN uses a transient (and typographically
ugly) form of direct definition.
Regarding the proposition
((~:/ . *.) -: (2 | +/ . *)) A
in your msg, I think you mean 2|-/ .* instead of
2|+/ .* . The latter expression +/ .* is the
permanent which has been proven to the intractable
(#P-complete; see the Wikipedia entry for
"permanent").
----- Original Message -----
From: Ewart Shaw <[EMAIL PROTECTED]>
Date: Monday, December 4, 2006 2:32 am
Subject: Re: [Jprogramming] monadic ~:/ . *.
> On Fri, 1 Dec 2006, Roger Hui wrote:
>
> > In SATN-42 (Sharp APL Technical Notes), 1982-04-01,
> > Ken Iverson described several uses monads derived
> > from the dot operator. Translated from APL into
> > J, these are:
> >
> > +./ . *.
> > + / . *.
> > <./ . +
> > >./ . +
> > <./ . *
> > >./ . *
> > <./ . >.
> > >./ . <.
>
> Many thanks for the reference. Have you any pointers as to
> how the above are used/can be useful? - I'm having a tough time
> understanding them! Needless (& sad) to say I couldn't find
> SATN-42 available anywhere.
>
> > Computation of f/ .g can be sped up for f and g
> > in domains which permit Gaussian elimination.
> > This has not been done in the current
> > implementation.
>
> I hope that general Gaussian elimination isn't too high up your list
> of priorities! Fortunately here the end-user, i.e. myself, can take
> advantage of J's existing Gaussian elimination because
>
> ((~:/ . *.) -: (2 | +/ . *)) A NB. A is square 0-1 matrix
> 1
>
> However, this won't work for a general finite field GF(q), where
> multiplication is not the same as q&|@*
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
