Oops, that's a rather bad problem. Here's a fixed version:
prim_alg2a =: verb define
mat =. y
size =. #y
list =. 0
pairs =: ''
while. (size > (# list)) do.
next =. (i. <./) ,|:_ list} list {"1 mat
'pndx newnode'=. (0,size)#: next
pairs =. pairs, < (pndx{list),newnode
lis
I just ran a couple of tests with prim_alg and prim_alg2, and it seems
prim_alg2 seems to fail for the following matrix:
mat3 =: 7 7 $ _ _ _ _ 12 34 19, _ _ 30 _ 14 _ 22, _ 30 _ 18 10 _ _, _ _ 18 _
40 27 11, 12 14 10 40 _ _ _, 34 _ _ 27 _ _ _, 19 22 _ 11 _ _ _
It's result:
┌───┬───┬───┬─
Similar, but exploiting Oblique instead of Suffix-Under-Reverse
(# {. ([ * +)//. & (]"0 1/~)) 1 0 1 1 1 1 0 1
1 0 1 2 3 4 0 1
I like this because I can watch the intermediate values flow from right to left.
And I can stare at the result of (]"0 1/~) until I understand what
Fun. For the skeptic -
+/ ( (2^~]) % 2&^) i.1e5
6
Not infinity but still can be used to validate
On Oct 24, 2014 11:32 AM, "Jon Hough" wrote:
> I was trying to remember how to solve a math problem the other day, and I
> got the chance to use the verb d. .
> The problem is
> find the sum(k=
On a tangentially related note:
It's usually worthwhile first coming up with something that works and then
(if performance is an issue) addressing the problems.
It's somewhat frightening, sometimes, how bad problems can be (and
honestly, in this example of minimum spanning tree code the problems
I should also note that
while. (size > (# list)) do.
can be replaced with
for. i. (#list)-1 do.
In other words, the contents of the loop needs to run once per edge in the
minimum spanning tree.
Thanks,
--
Raul
On Fri, Oct 24, 2014 at 12:25 PM, Raul Miller wrote:
> Yes, that had line w
Joe Bogner said:
"1. It's imperative style and doesn't feel like idiomatic J. I wonder ifit's
possible to use more of an array style (no loops)"
Yes, I realized that. I'm still not great at thinking only in arrays. But,
specifically for this problem, I'm not sure it is possible to do it without a
I just realized
(i. <./) ,|:_ list} list {"1 mat
does the removal. You put it much more tersely than I did.
> From: jgho...@outlook.com
> To: programm...@jsoftware.com
> Date: Fri, 24 Oct 2014 17:27:50 +0100
> Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm
>
> OK, than
OK, thanks. I think I understand prim_alg2.
The meat of it seems to be in:
next =. (i. <./) ,|:_ list} list {"1 mat
pairs =. pairs, < 'prevnode newnode'=. (0,size)#: next
I'm not sure how you are making sure no cycles form (the way I used the remove
verb), but your algorithm definitely works.I t
Right, definitions have a cost -- parsing for exampler. To demonstrate:
func=: 3 : 0
for_i. i.y do.
swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's.
swap _
end.
1
)
func2=: 3 : 0
swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's.
for_i. i.y do.
swap _
end.
Yes, that had line wrap problems, in comments.
Here's versions of the code with comments removed:
prim_alg =: verb define
list =. 0
pairs =: ''
mat =. y
size =. 0{ $ y
while. (size > (# list)) do.
swap =. (0&*)`(1&*)@.(1&=)
remove =. ,@:|:@:(_&(list}))@:(list&{"1)
next =. (I
That is still coming through garbled, for me.
So here's my attempt at posting your code:
mat0 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7 _ 9 _
prim_alg =: verb define
list =. 0 NB. list of already counted nodes (start at zero)
pairs =: '' NB. the pairs, i.e. edges
I see,
the verb swap should be outside the loop, but the way I defined remove, means
it needs to be redefined for each iteration (because list changes, I think).I'm
assuming redefining it inside the loop slows down the calculation?
> Date: Fri, 24 Oct 2014 12:09:07 -0400
> From: joebog...@gmail.
Argh, sent prematurely:
In terms of a code review, a few things:
1. It's imperative style and doesn't feel like idiomatic J. I wonder if
it's possible to use more of an array style (no loops)
2. You are defining some verbs in the loop. Seek to define verbs outside
the loop and only define nouns
In terms of a code review, a few things:
the first thing that jumps out to me is that you're defining some verbs in
your loop:
On Fri, Oct 24, 2014 at 11:57 AM, Jon Hough wrote:
> Here it is
>
>
>
> prim_alg =: verb define
>
> list =. 0 NB. list of already counted nodes (start at zero)
There is a couple of reasons it fails... First the simplest version uses just
one multiple to apply d to. In the case of S(x,10), that number is 6. It
relies on the hopeful conjecture that multiples of 6 will have more factors
than non multiples, and there is at least one multiple in every ran
Here it is
prim_alg =: verb define
list =. 0 NB. list of already counted nodes (start at zero)
pairs =: '' NB. the pair, i.e. edges, of the spanning tree.
mat =. yNB. distance matrix, infinity imlies not adjacent.
size =. 0{ $ y NB. Matrix must be square, so just g
Jon, can you resend without the extra line feeds?
You may need to paste as text or ctrl+shift+v
Pasting it into another editor, such as notepad and then copy/pasting from
there is another way to be sure it's plain text
On Fri, Oct 24, 2014 at 10:02 AM, Jon Hough wrote:
> Finding the minimum sp
That looks fun!
But I hope it's ok if I mention that d. is not a verb - it's a conjunction.
Thanks,
--
Raul
On Fri, Oct 24, 2014 at 11:32 AM, Jon Hough wrote:
> I was trying to remember how to solve a math problem the other day, and I got
> the chance to use the verb d. .
> The problem is
http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm looks better
suited for J.
Also perhaps relevant would be the directed graphs portion of
http://www.jsoftware.com/papers/tot.htm (that's a bit old, though, and
my browser does not deal properly with some of the notation - which is
APL rather
I was trying to remember how to solve a math problem the other day, and I got
the chance to use the verb d. .
The problem is
find the sum(k= 0, k = infinity) of (k^2)/(2^k)
I don't know the best way to solve it, the method I employed was to do:
define
S(x) as the sum(k= 0, k = infinity) of (k^2)
Finding the minimum spanning tree of a graph is (in theory) pretty easy.
I wanted to see if I could write Prim's algorithm in J.The algorithm is
conceptually simple: http://en.wikipedia.org/wiki/Prim's_algorithm , and I
thought it would not be too difficult to write in J. My attempt goes like thi
This might help see where it goes astray:
(~.,:#/.~)/:~ 10 >./\ dsieve 1000
4 6 8 9 10 12 14 15 16 18 20 21 24 27 28 30 32
2 12 24 12 16 174 16 20 245 158 102 10 160 10 10 10 10
+/ 10 >./\ dsieve 1000
17176
(~.,:#/.~)/:~991{.{. >./ ,:&> 0 -.~ [...] each boxes
4 6 8 9 10
23 matches
Mail list logo
