[Jprogramming] Arc consistency in J
Mike Day
mike_liz.day at tiscali.co.uk
Wed Nov 14 23:11:53 UTC 2012
Thanks, but my questions were rhetorical! I was merely trying to
comment on Linda's apparent aversion to @ and @: and her preference for
[: which she has justified in a later post. I'm not the Mike who
started this thread on arc consistency.
Incidentally, I also commented in that message on 11/11 (still in the
history below) about Raul Miller's question concerning the domain matrix D.
Mike
On 14/11/2012 11:24 AM, Linda Alvord wrote:
> Kip's comments are helpful.
>
> Back to your problem, Mike:
>
> X=:?(2#n)$2 NB. generate random matrix of [0,1]
> X=:X*(i.n)</i.n NB. make it upper diagonal, zeros on diagonal
> ]X=:X+|:2*X
> 0 0 0 0 1
> 0 0 1 0 0
> 0 2 0 0 0
> 0 0 0 0 1
> 2 0 0 2 0
>
> The three lines can be combined in one line.
>
> ]X+|:2*X=:(?(2#n)$2)*(i.n)</i.n
> 0 1 1 0 1
> 2 0 1 0 1
> 2 2 0 1 0
> 0 0 2 0 0
> 2 2 0 0 0
>
> Linda
>
>
> -----Original Message-----
> From: programming-bounces at forums.jsoftware.com [mailto:programming-bounces at forums.jsoftware.com] On Behalf Of km
> Sent: Wednesday, November 14, 2012 4:29 AM
> To: programming at jsoftware.com
> Subject: Re: [Jprogramming] Arc consistency in J
>
> Responding to Mike's query about @
>
> Mathematical composition f o g means "do g first, then f" and is expressed in J by the monadic use of f @: g or [: f g . The monadic use of f @ g can surprise you, compare
>
> |.@:+: 1 2 3
> 6 4 2
> |. at +: 1 2 3
> 2 4 6
>
> -- the first means double vector 1 2 3 then reverse the resulting vector, the second means double and reverse each scalar then assemble the results.
>
> Kip Murray
>
> Sent from my iPad
>
>
> On Nov 13, 2012, at 8:44 PM, "Linda Alvord" <lindaalvord at verizon.net> wrote:
>
>> 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-bounces at forums.jsoftware.com
>> [mailto:programming-bounces at forums.jsoftware.com] On Behalf Of Mike
>> Day
>> Sent: Monday, November 12, 2012 6:40 AM
>> To: programming at 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-bounces at forums.jsoftware.com
>>> [mailto:programming-bounces at forums.jsoftware.com] On Behalf Of Mike
>>> Day
>>> Sent: Sunday, November 11, 2012 7:15 AM
>>> To: programming at 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-bounces at forums.jsoftware.com
>>> [mailto:programming-bounces at forums.jsoftware.com] On Behalf Of Raul
>>> Miller
>>> Sent: Saturday, November 10, 2012 12:44 PM
>>> To:programming at jsoftware.com
>>> Subject: Re: [Jprogramming] Arc consistency in J
>>>
>>> On Sat, Nov 10, 2012 at 12:16 PM, Michal
>>> D.<michal.dobrogost at 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
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
More information about the Programming
mailing list