Mike, I'll try again... Maybe it's because I'm left handed that I prefer to avoid @ .
When I see ((<@#)&(i.n))@(0&<) or (0 < ]) ([: < #)"1 [: i. # I am looking at a foreign language. When I see this '(0<y)([:<#)"1 i.#y' I know to begin with one argument rather than two! I also see that (0<y) is at the end in the first terse version and at the beginning in the second. Also, i.# is on the right in the second version. However, it not as noticeable in the first. f So, as a teacher, I always struggle to write only in explicit, slow steps building a solution from the right to the left. Unlike that last sentence, I build from right to left. After years of looking at these two versions I don't read either well. I'm a slow reader and a good proof reader. So, I use either to pick out the verbs I should use to get specific results. I build from right to left. I keep the explicit version so I won't have to struggle to remember where the arguments belong. Thus I try to simplify for myself and for beginners. In the long run the programmers tend to like the first version and the mathematicians will read and write from right to left. Heavy use of @ tells me which way you, the writer, are headed. Linda From: [email protected] [mailto:[email protected]] On Behalf Of Linda AlvordSent: Monday, November 12, 2012 2:57 AM To: [email protected] Subject: Re: [Jprogramming] Arc consistency in J 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. . t 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: [email protected] [mailto:[email protected]] On Behalf Of Mike Day Sent: Sunday, November 11, 2012 7:15 AM To: [email protected] 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:[email protected] [mailto:[email protected]] On Behalf Of Raul Miller Sent: Saturday, November 10, 2012 12:44 PM To:[email protected] Subject: Re: [Jprogramming] Arc consistency in J On Sat, Nov 10, 2012 at 12:16 PM, Michal D.<[email protected]> 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
