I can only give a personal response. Maybe it is because I'm left handed. When I look at ((<@#)&(i.n))@(0&<) at or
-----Original Message----- From: programming-boun...@forums.jsoftware.com [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day Sent: Monday, November 12, 2012 6:40 AM To: programm...@jsoftware.com Subject: Re: [Jprogramming] Arc consistency in J But what's wrong with @ that's preferable with [: ? (I think Th is has been asked before.) Aren't they both devices to represent what "ordinary" mathematicians just write as f g h ... for the composition of f g h ... ? Since J cleverly allows hooks and forks and interprets unbracketed trains of verbs as such, it needs some other way to recognise composition, and that's what both @ (and @:) and [: do for us - so why avoid one or the other of them? I agree it took a lot of time to get my head round the new way of seeing trains of verbs. Mike On 12/11/2012 7:57 AM, Linda Alvord wrote: > Well, it was possible, once I managed to get the rank right. Thanks > for providing hope that it could be done. Actually it is not too bad > looking after all. > > A > 0 0 1 0 0 > 0 0 0 0 0 > 2 0 0 0 1 > 0 0 0 0 1 > 0 0 2 2 0 > > adj=:((<@#)&(i.n))@(0&<) > adj > <@#&0 1 2 3 4@(0&<) > adj A > --TT---T-T---┐ > │2││0 4│4│2 3│ > L-++---+-+---- > > f=: 13 :'(0<y)([:<#)"1 i.#y' > f > (0 < ]) ([: < #)"1 [: i. # > f A > --TT---T-T---┐ > │2││0 4│4│2 3│ > L-++---+-+---- > > 5!:4 <'adj' > -- < > -- @ -------+- # > -- & -+- 0 1 2 3 4 > │ > -- @ -+ -- 0 > L- & -+- < > > 5!:4 <'f' > -- 0 > ------+- < > │ L- ] > │ -- [: > │ -----+- < > --+- " -+ L- # > │ L- 1 > │ > │ -- [: > L-----+- i. > L- # > > Linda > > -----Original Message----- > From: programming-boun...@forums.jsoftware.com > [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike > Day > Sent: Sunday, November 11, 2012 7:15 AM > To: programm...@jsoftware.com > Subject: Re: [Jprogramming] Arc consistency in J > > I don't think you can remove the @, although you may use the cap, [: , > instead, but then you need to force the rank: > ([:<(#&0 1 2 3@(0&<)))"1 A > +-++---+-+ > |2||0 3|2| > +-++---+-+ > > I don't like using 0 1 2 3 explicitly since it presumes you know the > dimension of A, so I prefer either > adja =: * <@# i.@# NB. or use caps if @ is too horrible > adja A > +-++---+-+ > |2||0 3|2| > +-++---+-+ > > or > > adjI =: <@I.@:* > adjI A > +-++---+-+ > |2||0 3|2| > +-++---+-+ > > I. is so useful that I've defined an I "dfn" in my Dyalog APL too! > > As for Raul's point about D, I understood it to represent the domains > of the variables: if there are m variables and the domain of all > their possible values is i.n, then 1 = D{~<i,j means that variable > number i may have value j . m and n are likely to be different. So > i<D is a boolean representing the a priori values that variable i might have. > The consistency algorithm apparently examines which of these a priori > values are consistent with the domains of the other variables given > certain unary and binary constraints which are also inputs to the problem. > > Michal's example had m=n which tends to mislead the casual reader! > > I believe The m*m A array points to which constraints apply, so > 0<l=A{<i,k means that binary constraint number l applies between variables i and k. > This is why A isn't just a boolean adjacency matrix nor do the entries > signify distances as they would in a weighted graph. > > I'm puzzled that the algorithm requires each binary relation to be > presented in both direct and transposed form (this explains Michal's > need to patch in a new index (to a transposed C) in the lower triangle > of A for each index to a direct C in the upper triangle). Perhaps the later algorithms (arc-4... > ?) deal with this difficulty. > > It strikes me that for a real problem, concise relations such as x <: > y, or 2x+3y>5 can become pretty large and unwieldy C-tables, but > perhaps that's unavoidable when working in the integers. > > (The other) Mike > > On 11/11/2012 10:16 AM, Linda Alvord wrote: > > Mike, I think this will work as an alternative to adj > > A > 0 0 1 0 > 0 0 0 0 > 2 0 0 1 > 0 0 2 0 > adj > <@#&0 1 2 3@(0&<) > adj A > --TT---T-┐ > │2││0 3│2│ > L-++---+-- > h > 0 1 2 3 <@#~ 0 < ] > h A > --TT---T-┐ > │2││0 3│2│ > L-++---+-- > > Can anyone remove the final @ from h ? > > Linda > > > -----Original Message----- > From:programming-boun...@forums.jsoftware.com > [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul > Miller > Sent: Saturday, November 10, 2012 12:44 PM > To:programm...@jsoftware.com > Subject: Re: [Jprogramming] Arc consistency in J > > On Sat, Nov 10, 2012 at 12:16 PM, Michal > D.<michal.dobrog...@gmail.com> > wrote: > >> Here X is telling us to use the constraint c1 (presumably b/c C is >> not >> shown) between the variables 1 and 3 (0 based). Likewise, use the >> transpose going the other direction (3,1). > Ouch, you are correct, I did not specify C. On retesting, though, it > looks like my results stay the same when I use: > > arccon=:3 :0 > 'D c1 X'=: y > 'n d'=: $D > adj =: ((<@#)&(i.n)) @ (0&<) > A =: adj X > C=: a: , c1 ; (|:c1) > ac =: > @ (1&{) @ (revise^:_) @ ((i.n)&;) > ac D > ) > > For longer scripts like this, I really need to get into the habit of > restarting J for every test. So that probably means I should be using jhs. > >> Given the structure of X, only variables 1 and 3 can possibly change. >> So if they are all changing something is definitely wrong. > This line of thinking does not make sense to me. I thought that the > requirement was that a 1 in D exists only when there is a valid > relationship along a relevant arc. If a 1 in D can also exist in the > absence of any relevant arc, I am back to needing a description of the algorithm. > >> Unfortunately I've run out of time to read the rest of your response >> but hopefully I can get through it soon. I've also wanted to write a >> simpler version of the algorithm where the right argument of ac is >> only D and it runs through all the arcs in the problem instead of >> trying to be smart about which ones could have changed. > Yes... I am currently suspicious of the "AC-3 algorithm". > > In the case of symmetric consistency, I think that it's unnecessary > complexity, because the system converges on the initial iteration. > > In the case of asymmetric consistency, I think that the work involved > in maintaining the data structures needed for correctness will almost > always exceed the work saved. > > But I could be wrong. I am not sure yet if I understand the > underlying algorithm! > > -- > Raul > > ---------------------------------------------------------------------- > 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
