You can follow the highlighting better if you do dissect '(2 2 $ 3 5 7 1) <./@(+"1 _) 2 2 $ 3 5 7 1'
Henry Rich On 10/30/2014 4:44 PM, Henry Rich wrote: > No, you're not doing > > r =. m +"(1 _) m > > followed by > > m <./ r > > The <./ is applied on each result cell of m +"(1 _) m individually, and > those results are assembled into the final result. > > Dissect doesn't look inside u .v, but you could try > > dissect '<./@(+"1 _)~ 2 2 $ 3 5 7 1' > > Henry Rich > > On 10/30/2014 9:25 AM, Jon Hough wrote: >> Unfortunately, even after reading the Nuvoc entry for . , I'm not sure I get >> it.I was messing around with some usages: >> >> f =. <./ . + >> >> >> >> >> m =: 2 2 $ 3 5 7 1 >> >> >> f~ m >> >> >> this gives >> >> >> 6 6 >> >> >> 8 2 >> >> >> Which seems odd. From Nuvoc, "x u . v y is defined for general u and v as x >> u@(v"(1+lv,_)) y". >> >> >> So here I am doing m +"(1 _) m >> >> >> and then from using the result of that, r say, doing >> >> >> m <./ r >> >> >> But the result of doing that is clearly not what is wanted. >> >> >> >> >> >> >> >>> Date: Thu, 30 Oct 2014 06:58:31 -0400 >>> From: [email protected] >>> To: [email protected] >>> Subject: Re: [Jprogramming] Algorithm to Check Graph is connected >>> >>> It looks like a hook because of the spacing and because .+ looks like a noun >>> >>> . is a conjunction, and returns a derived verb. As such there are two verbs >>> in the train, so a fork >>> >>> (<./ . +) >>> u . v >>> >>> uu=: </. >>> vv=: + >>> >>> (<. (uu . vv)) ~ (3 3 $ i.3) >>> >>> >>> running trace can be helpful: >>> >>> trace '(<. <./ . +)~ arr' >>> --------------- 3 Adverb ----- >>> <. >>> / >>> <./ >>> --------------- 4 Conj ------- >>> <./ >>> . >>> + >>> <./ .+ >>> --------------- 6 Bident ----- >>> <. >>> <./ .+ >>> <. <./ .+ >>> --------------- 8 Paren ------ >>> ( >>> <. <./ .+ >>> ) >>> <. <./ .+ >>> --------------- 3 Adverb ----- >>> <. <./ .+ >>> ~ >>> (<. <./ .+)~ >>> --------------- 6 Bident ----- >>> (<. <./ .+)~ >>> arr >>> (<. <./ .+)~ arr >>> ============================== >>> >>> >>> >>> >>> >>> >>> On Thu, Oct 30, 2014 at 1:56 AM, Raul Miller <[email protected]> wrote: >>> >>>> It's a hook. >>>> >>>> The dot needs a space to its left to prevent it binding with the slash. >>>> >>>> (Insert slashdot joke, here.) >>>> >>>> Thanks, >>>> >>>> -- >>>> Raul >>>> >>>> >>>> On Thu, Oct 30, 2014 at 1:49 AM, Jon Hough <[email protected]> wrote: >>>>> Is (<. <./ .+)〜 a fork? It looks like it should be a fork, but running >>>> dissect on it shows a hook. >>>>> >>>>> >>>>> --- Original Message --- >>>>> >>>>> From: "Henry Rich" <[email protected]> >>>>> Sent: October 30, 2014 11:02 AM >>>>> To: [email protected] >>>>> Subject: Re: [Jprogramming] Algorithm to Check Graph is connected >>>>> >>>>> Only one small tweak to this fine post: >>>>> >>>>> > The rough J equivalent of C's array[i][j] = 30; would be >>>>> > >>>>> > 30 (<i,j)} array >>>>> >>>>> Precisely (Raul said 'rough', but the subtlety may be lost on >>>>> beginners), the equivalent would be >>>>> >>>>> array =: 30 (<i,j)} array >>>>> >>>>> 30 (<i,j)} array makes a whole new copy of array with element (i,j) >>>>> changed. This can be expensive if the array is large. By assigning to >>>>> the same name you save the cost of the new copy. >>>>> >>>>> Henry Rich >>>>> >>>>> On 10/29/2014 8:09 PM, Raul Miller wrote: >>>>>> The rough J equivalent of C's array[i][j] = 30; would be >>>>>> >>>>>> 30 (<i,j)} array >>>>>> >>>>>> For example: >>>>>> 30 (<2 3)} 6 6$0 >>>>>> 0 0 0 0 0 0 >>>>>> 0 0 0 0 0 0 >>>>>> 0 0 0 30 0 0 >>>>>> 0 0 0 0 0 0 >>>>>> 0 0 0 0 0 0 >>>>>> 0 0 0 0 0 0 >>>>>> >>>>>> That said, be aware that often (not always, but often enough to be >>>>>> worth discussing the algorithm) J will offer better approaches. >>>>>> >>>>>> For example, for your connectedness problem: >>>>>> mat1 =: 5 5 $ _ 3 4 2 _, 3 _ _ 1 8, 4 _ _ 5 5, 2 1 5 _ _, _ 8 5 _ _ >>>>>> mat2 =: 3 3 $ _ 1 _, 1 _ _, _ _ _ >>>>>> >>>>>> (<. <./ .+~)~^:# mat1 >>>>>> 4 3 4 2 9 >>>>>> 3 2 6 1 8 >>>>>> 4 6 8 5 5 >>>>>> 2 1 5 2 9 >>>>>> 9 8 5 9 10 >>>>>> (<. <./ .+~)~^:# mat2 >>>>>> 2 1 _ >>>>>> 1 2 _ >>>>>> _ _ _ >>>>>> >>>>>> The expression (<. <./ .+)~^:_ finds the path distance between every >>>>>> pair of points in your distance matrix. If any of them are _ the >>>>>> matrix is not connected. >>>>>> >>>>>> _ e. , (<. <./ .+)~^:_ mat1 >>>>>> 0 >>>>>> _ e. , (<. <./ .+)~^:_ mat2 >>>>>> 1 >>>>>> >>>>>> The expression (<. <./ .+)~^:# is a slightly less efficient version of >>>>>> (<. <./ .+)~^:_ >>>>>> >>>>>> The difference is that # specifies a repeat count equal to the number >>>>>> of rows in the matrix, while _ stops as soon as the result converges. >>>>>> To see why this matters, it can be instructive to look at some >>>>>> examples. You can see all the intermediate results (as well as initial >>>>>> and final values) by using a: instead: >>>>>> >>>>>> (<. <./ .+~)~^:a: mat1 >>>>>> _ 3 4 2 _ >>>>>> 3 _ _ 1 8 >>>>>> 4 _ _ 5 5 >>>>>> 2 1 5 _ _ >>>>>> _ 8 5 _ _ >>>>>> >>>>>> 4 3 4 2 9 >>>>>> 3 2 6 1 8 >>>>>> 4 6 8 5 5 >>>>>> 2 1 5 2 9 >>>>>> 9 8 5 9 10 >>>>>> >>>>>> and >>>>>> >>>>>> (<. <./ .+~)~^:a: mat2 >>>>>> _ 1 _ >>>>>> 1 _ _ >>>>>> _ _ _ >>>>>> >>>>>> 2 1 _ >>>>>> 1 2 _ >>>>>> _ _ _ >>>>>> >>>>>> The final result was achieved on the first iteration in both examples. >>>>>> >>>>>> So... how does that expression work? >>>>>> >>>>>> Structurally, it's doing something very like a transitive closure. See >>>>>> example 5 in the dictionary entry for ^: >>>>>> >>>>>> http://jsoftware.com/help/dictionary/d202n.htm >>>>>> >>>>>> Except, each iteration, it's adding every pair between two copies of >>>>>> the distance matrix and then for each endpoint pair finding the >>>>>> minimum distance which resulted. And, for sanity's sake, taking the >>>>>> minimum of that result and the original pair distance. >>>>>> >>>>>> The tricky part, if you have not seen it before, is the inner product: >>>>>> u/ .v >>>>>> >>>>>> Matrix multiplication is +/ .* and we are following the same pattern >>>>>> here. Rather than try to document the details, however, I would prefer >>>>>> to point you at the dictionary >>>>>> http://jsoftware.com/help/dictionary/d202n.htm and the nuvoc page >>>>>> http://www.jsoftware.com/jwiki/Vocabulary/dot#dyadic >>>>>> >>>>>> (The other thing I am using is the u~ pattern. That's even simpler: >>>>>> u~y is equivalent to y u y. So, +~1 is equivalent to 1+1. Actually, >>>>>> it's so simple that it's worth explaining just because otherwise it's >>>>>> something your eyes might gloss over.) >>>>>> >>>>>> Anyways, unless you are working with connection matrices which stress >>>>>> the capacity of your machine, I imagine that finding all the path >>>>>> distances and checking if any are infinity will be faster than your >>>>>> >>>>>> connected =: verb define >>>>>> mat=: y NB. the graph (square matrix) >>>>>> in=: 0 NB. list of connected nodes, start at node 0. >>>>>> size=: # y NB. Size of y >>>>>> all=: i. size NB. all nodes. >>>>>> isconnected =: 0 NB. is connected flag. >>>>>> counter =: 0 >>>>>> NB. loop through all nodes in graph. >>>>>> NB. Add any nodes connected to the in list to the in list. >>>>>> NB. If connected, in will eventually contain every node. >>>>>> while. (counter < size) do. >>>>>> counter=: counter + 1 NB. increment counter (very bad J?). >>>>>> toin =: '' >>>>>> NB. only want nodes that may not be connected. (remove "in" nodes) >>>>>> for_j. all -. in do. >>>>>> NB. Get each column from in list and find non-infinite >>>>>> NB. edges from these nodes to nodes in all - in list. >>>>>> NB. (%) is to convert _ to 0. >>>>>> if. ((+/@:%@:(j &{"2) @: (in& { "1) mat ) > 0) do. >>>>>> toin =: toin , j >>>>>> end. >>>>>> end. >>>>>> NB. append toin to in. Number of connected nodes increases. >>>>>> in =: ~. in, toin >>>>>> NB. check connectivity. >>>>>> isconnected =:-. (# in ) < size >>>>>> if. isconnected do. >>>>>> end. >>>>>> end. >>>>>> isconnected >>>>>> ) >>>>>> >>>>>> I hope this helps, >>>>>> >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> ---------------------------------------------------------------------- >>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
