Note that ?. might give different results in different versions of J. It's designed to be a convenience, nothing more.
Thanks, -- Raul On Sat, Feb 16, 2013 at 12:06 PM, Mike Day <[email protected]> wrote: > Yes! Similar results here, though I'm a bit puzzled that graph3 doesn't > seem to yield quite the same counts: > > graph3=:0=?.2000 2000$1000 NB. try to reproduce Raul's latest graph, > but with results inconsistent with his!? > > timer'(,:#@(] graph3 wrap & 0)"0) ]>:i.6'NB. using Raul's wrap. N=7 > takes too long.... > +-----+-----------------+ > |9.729|1 2 3 4 5 6| > | |1 5 15 40 107 301| > +-----+-----------------+ > > $ones=:;pairs graph3 NB. from Kim Murray > 4005 2 > > timer'$;@:next^:3 ones' NB. from Kim Murray: create all directed paths, > including cycles, with four moves > +---+--------+ > |6.5|539791 5| > +---+--------+ > > timer'(,:#@(] graph3 wrapc & 0)"0) ]>:i.10' NB. using my wrapc - gets a > bit further before exploding > +--------+--------------------------------------+ > |0.573975|1 2 3 4 5 6 7 8 9 10| > | |1 5 15 40 107 301 911 2999 10753 41576| > +--------+--------------------------------------+ > > */\inv 1 5 15 40 107 301 911 2999 10753 41576 NB. explore the scaling > factors for origin 0 > 1 5 3 2.66667 2.675 2.81308 3.02658 3.29199 3.58553 3.86646 > > (,:#@(] graph3 wrapc & 1)"0) ]>:i.10 NB. !!!!!trivial for origins with > low connectivity > 1 2 3 4 5 6 7 8 9 10 > > 1 1 1 0 0 0 0 0 0 0 > > timer'(,:#@(] graph3 wrapc & 2)"0) ]>:i.9' NB. blows up for N=9 > |out of memory: timer > | p=. /:~"1 p,.0-.~,to > > timer'(,:#@(] graph3 wrapc & 2)"0) ]>:i.8'NB. so try N=1...8 > +--------+-----------------------------+ > |0.398193|1 2 3 4 5 6 7 8| > | |1 4 18 85 405 1875 8574 39166| > +--------+-----------------------------+ > > */\inv 1 4 18 85 405 1875 8574 39166 NB. and scaling factors for origin > 2 > 1 4 4.5 4.72222 4.76471 4.62963 4.5728 4.568 > > Where now? There _might_ be some gain by first producing all directed > acyclic paths of a certain length, and then pruning and joining them, but > that would probably suffer with problems with partitioning. I suppose Kip > is doing this sort of thing, except that he's allowing cycles of all sizes > including length-1 loops, and his approach also runs out of memory at > around N=6. (He is of course building paths from all nodes in the graph). > > Mike > (now that I've finished the Times/Listener crossword, "Cleopatra's Needled") > > > > On 16/02/2013 1:52 PM, Raul Miller wrote: >> >> Actually, thinking about this, a path length of 100 is probably >> unreasonable to measure precisely. >> >> Here's an example case: >> >> graph=: 0=?.2000 2000$1000 >> $I.1 graph wrap 0 >> 1 1 >> $I.2 graph wrap 0 >> 4 2 >> >> I'm being experimental here, reissuing lines, and it's inconvenient to >> edit in the middle of the line, so: >> >> $I.(] graph wrap 0:)2 >> 4 2 >> $I.(] graph wrap 0:)3 >> 16 3 >> $I.(] graph wrap 0:)4 >> 69 4 >> $I.(] graph wrap 0:)5 >> 317 5 >> $I.(] graph wrap 0:)6 >> 1548 6 >> >> I can roughly approximate the growth rate of the size of the data >> using 4^(N-1) - the actual growth rate looks slightly higher than >> that. >> >> So, >> 4^100x >> 1606938044258990275541962092341162602522202993782792835301376 >> >> I do not think I have enough memory to represent a result of that size. >> >> But, wait, at some point the graph representation will run out of >> possibilities to represent, which will restrict the growth of the data >> set. So, what does that limit look like? >> >> 2^2000x >> >> 1148130695274254524232833201177681984022317702088695200477642736825766261392370313856659486316506269918445964638987462773447118960863055331425931356166653185391299891453122800006887791482400448714289269900634862447816154636463883639473170260404663539709049... >> >> ... oh ... >> >> New implementation: >> >> ((+/%#)+/graph)^100 >> 3.26311e30 >> >> That's probably accurate to within a few powers of 10... >> > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
