Hi Raul,
Could you provide some context in which to run this code?
Thanks,
Mike
On Fri, Nov 16, 2012 at 6:52 PM, Raul Miller <rauldmil...@gmail.com> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
