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-boun...@forums.jsoftware.com
[mailto: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-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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
