If you are talking about my post on the 10th, where I proposed
arcn=:3 :0
'D c1 X'=: y
X1=. 1=X
([:+./"1[: +./((|:c1) *"1 2~ (|:X1) *"1 2 ]) +. c1 *"1 2~ X1 *"1 2 ])^:_ D
)
... note that it works just fine when D is not square.
And all I got out of Mike's 11/11 message was that D might not be square.
Am I missing something?
--
Raul
P.S. In the above code, X1=. 1 = X assumes that X had only 2s and 0s
in the lower triangle. Perhaps a better expression would have been X1
=. (*X) * </&i./ $X
On Fri, Nov 16, 2012 at 9:44 PM, Michal D. <michal.dobrog...@gmail.com> wrote:
> Boss is Boss, I eventually arrived at the same (non-negative case) solution.
>
> Thanks km for the explanation of @ vs @: which I'm starting to slowly get.
>
> Linda: I think I prefer having it on three lines. It better breaks down
> the steps I'm trying to accomplish. Maybe someday I'll be able to boil it
> down to a single line ;-)
>
> Raul: please let me know if we should still pursue your previous definition
> in light of Mike's commentary.
>
> Mike Day is right on with all his observations about what I'm trying to
> accomplish. Sorry for the long delay - I'm having trouble keeping up.
> Notes:
>
> (0) Interesting {:: vs { and <
>
> (1) The J arc consistency algorithm I've presented is not AC-3 nor any of
> the later AC algorithms. AC-3 is simply another algorithm that
> accomplishes the same thing.
>
> (2) Using the approach I do with the C-tables allows massive parallelism.
> In particular using mostly logical-and and logical-or operations on boolean
> arrays allows a single assembly level operation to have 32 or 64 way
> parallelism (or larger if using vector registers).
>
> (3) A simpler algorithm that requires a single version of each C-table and
> a revDom that reduces both it's input domains is possible but I haven't
> gotten there yet. I'm working on it along with code to randomly generate a
> sudoku and generate the equivalent CSP. It might be a while.
>
> Cheers,
>
> Mike
>
>
> On Wed, Nov 14, 2012 at 3:11 PM, Mike Day <mike_liz....@tiscali.co.uk>wrote:
>
>> 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@forums.**jsoftware.com<programming-boun...@forums.jsoftware.com>[mailto:
>>> programming-bounces@**forums.jsoftware.com<programming-boun...@forums.jsoftware.com>]
>>> On Behalf Of km
>>> Sent: Wednesday, November 14, 2012 4:29 AM
>>> To: programm...@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
>>> |.@+: 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" <lindaalv...@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@forums.**jsoftware.com<programming-boun...@forums.jsoftware.com>
>>>> [mailto:programming-bounces@**forums.jsoftware.com<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-bounces@forums.**jsoftware.com<programming-boun...@forums.jsoftware.com>
>>>>> [mailto:programming-bounces@**forums.jsoftware.com<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-bounces@**forums.jsoftware.com<from%3aprogramming-boun...@forums.jsoftware.com>
>>>>> [mailto:programming-bounces@**forums.jsoftware.com<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<http://www.jsoftware.com/forums.htm>
>>>>> ------------------------------**------------------------------**
>>>>> ---------
>>>>> - For information about J forums see
>>>>> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>>>>>
>>>> ------------------------------**------------------------------**
>>>> ----------
>>>> For information about J forums see
>>>> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>>>>
>>>> ------------------------------**------------------------------**
>>>> ----------
>>>> For information about J forums see
>>>> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>>>>
>>> ------------------------------**------------------------------**
>>> ----------
>>> For information about J forums see
>>> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>>>
>>> ------------------------------**------------------------------**
>>> ----------
>>> For information about J forums see
>>> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>>>
>>
>> ------------------------------**------------------------------**----------
>> For information about J forums see
>> http://www.jsoftware.com/**forums.htm<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
