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
