I finally wrote f without @ ]A=:?3 3$3 0 0 2 0 0 0 0 2 1 f=: 13 :'(0<y)<@#i.#y' f (0 < ]) <@# [: i. # f A --TT---┐ │2││1 2│ L-++---- g=: 13 :'(0<y)([:<#)"1 i.#y' g (0 < ]) ([: < #)"1 [: i. # g A --TT---┐ │2││1 2│ L-++---- I think it came to me after the recent discussion about @: and capped fork.
Linda -----Original Message----- From: programming-boun...@forums.jsoftware.com [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Linda Alvord Sent: Sunday, November 11, 2012 1:56 PM To: programm...@jsoftware.com Subject: Re: [Jprogramming] Arc consistency in J Mike, I changed f as you suggest. n=: 5 A=:?(2#n)$2 NB. generate random matrix of [0,1] A=:A*(i.n)</i.n NB. make it upper diagonal, zeros on diagonal ]A=:A+|:2*A 0 0 1 0 0 0 0 0 0 0 2 0 0 1 1 0 0 2 0 1 0 0 2 2 0 adj=:((<@#)&(i.n))@(0&<) adj <@#&0 1 2 3 4@(0&<) adj Al --TT-----T---T---┐ │2││0 3 4│2 4│2 3│ L-++-----+---+---- f=: 13 :'(0<y)<@#i.#y' f (0 < ]) <@# [: i. # f A --TT-----T---T---┐ │2││0 3 4│2 4│2 3│ L-++-----+---+---- I'm still hoping to remove @ and I guess it will be useful to deal with rank as Henry suggests. I think I'll take a second look at A. Thanks for all your help. 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