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
