Raul, There is a time and space report below for "four moves", failure came on "five moves".
My iPad reports 55.3 GB available memory. A crash report for the "five moves" failure says reserved pages for the J process were 73234, "recent max" was 73253. There may have been an interruption from "MobileMail" which was using 34618 pages at the time. Page usage of most other processes was in the hundreds with three or four in the thousands up to 5500. I am way out of my comfort zone here, not understanding what I am reporting or whether it is relevant! Kip Sent from my iPad On Feb 16, 2013, at 7:36 AM, Raul Miller <[email protected]> wrote: > It's hard for me to understand this "out of memory" state without > knowing how much memory your machine has, or how much gets used in the > successful cases. > > Thanks, > > -- > Raul > > On Sat, Feb 16, 2013 at 1:03 AM, km <[email protected]> wrote: >> iPad time and space results for Kip's code. Brian Schott tells me correctly >> that verb open can be replaced by verb Raze ; >> >> ones =: ; pairs 1 = ?. 200 200 $ 100 NB. paths with one move >> # ones >> 390 >> 5 {. ones NB. each pair represents one move >> 1 8 >> 1 9 >> 2 41 >> 2 44 >> 2 84 >> >> ts ';@:next^:3 ones' NB. create all paths with four moves >> 0.694511 2.89005e6 >> >> ts ';@:next^:4 ones' NB. create all paths with five moves >> |out of memory: ts >> | ;@:next^:4 ones >> >> fours =: ;@:next^:3 ones NB. all paths with four moves >> #fours >> 45601 >> 5 {. fours NB. each five-tuple represents four moves >> 1 8 37 13 151 >> 1 8 37 13 186 >> 1 8 37 13 49 >> 1 8 37 13 71 >> 1 8 37 13 192 >> >> Kip Murray >> >> Sent from my iPad >> >> On Feb 15, 2013, at 6:23 PM, km <[email protected]> wrote: >>> >>> P.S. I do not expect my directed graph code to be efficient for large >>> graphs and long chains, but I will experiment and report back. >>> >>> Sent from my iPad >>> >>> >>> On Feb 15, 2013, at 3:30 PM, Raul Miller <[email protected]> wrote: >>> >>>> How does your code fair with large (sparsely connected) graphs and >>>> large visitable sets? >>>> >>>> Thanks, >>>> >>>> -- >>>> Raul >>>> >>>> On Fri, Feb 15, 2013 at 4:19 PM, km <[email protected]> wrote: >>>>> Raul, >>>>> >>>>> I have carefully ignored your later posts and may be on a different track >>>>> than you intended. Here is where I am. Path 1 8 6 means there is a >>>>> directed edge from 1 to 8 and a directed edge from 8 to 6 and is >>>>> different from path 1 6 8 if such a path exists. You can even have a one >>>>> edge path 7 7 which loops from 7 to 7. Notice my use of ^: Power in the >>>>> last sentence of this long post. >>>>> >>>>> Kip Murray >>>>> >>>>> ]graph=: 2 > ?. 10 10 $ 10 NB. Raul had 20 20 $ 10 >>>>> 0 0 0 0 0 0 1 0 1 0 >>>>> 0 0 0 0 1 0 0 1 1 0 >>>>> 1 0 1 0 0 1 0 0 0 0 >>>>> 0 0 0 0 0 1 0 0 0 0 >>>>> 1 0 0 0 0 0 0 0 0 0 >>>>> 0 0 0 0 0 0 0 0 0 0 >>>>> 0 0 0 0 0 0 0 0 1 0 >>>>> 0 1 0 0 0 0 0 1 0 0 >>>>> 0 0 0 0 0 0 1 0 0 0 >>>>> 0 0 0 0 0 0 0 0 0 0 >>>>> >>>>> NB. A 1 in row p column q indicates a directed edge from p to q >>>>> >>>>> edges =: [: I.&.> <"1 NB. utility >>>>> >>>>> edges graph >>>>> +---+-----+-----+-+-++-+---+-++ >>>>> |6 8|4 7 8|0 2 5|5|0||8|1 7|6|| >>>>> +---+-----+-----+-+-++-+---+-++ >>>>> >>>>> pairs =: i.@# ,.&.> edges NB. utility >>>>> >>>>> pairs graph >>>>> +---+---+---+---+---+--+---+---+---+--+ >>>>> |0 6|1 4|2 0|3 5|4 0| |6 8|7 1|8 6| | >>>>> |0 8|1 7|2 2| | | | |7 7| | | >>>>> | |1 8|2 5| | | | | | | | >>>>> +---+---+---+---+---+--+---+---+---+--+ >>>>> >>>>> open =: 3 : '> ,&.>/(-. (0, {: $ > 0 { y) -:"1 $&> y)#y' NB. utility >>>>> >>>>> ]twos =: open pairs graph NB. directed edges from 0 to 6, 0 to 8 and so >>>>> on >>>>> 0 6 >>>>> 0 8 >>>>> 1 4 >>>>> 1 7 >>>>> 1 8 >>>>> 2 0 >>>>> 2 2 >>>>> 2 5 >>>>> 3 5 >>>>> 4 0 >>>>> 6 8 >>>>> 7 1 >>>>> 7 7 >>>>> 8 6 >>>>> >>>>> NB. no edge from 5 or 9, no edge to 3 or 9 >>>>> >>>>> NB. there is an edge from 7 to 7 (a one-edge loop) >>>>> >>>>> more =: 4 : '~. y ,"1 0 {:"1 (({:y) = {."1 x)# x' NB. x is an open >>>>> table, y is a table row >>>>> >>>>> next =: 3 : 'y&more &.> <"1 y' NB. y is table of paths, result is boxed >>>>> one longer paths >>>>> >>>>> countpaths =: 4 : '+/ y = {."1 x' NB. count paths in open x that begin >>>>> with y >>>>> >>>>> ]threes =: open next twos NB. paths from 0 to 6 to 8, from 0 to 8 to 6, >>>>> and so on >>>>> 0 6 8 >>>>> 0 8 6 >>>>> 1 4 0 >>>>> 1 7 1 >>>>> 1 7 7 >>>>> 1 8 6 >>>>> 2 0 6 >>>>> 2 0 8 >>>>> 2 2 0 >>>>> 2 2 2 >>>>> 2 2 5 >>>>> 4 0 6 >>>>> 4 0 8 >>>>> 6 8 6 >>>>> 7 1 4 >>>>> 7 1 7 >>>>> 7 1 8 >>>>> 7 7 1 >>>>> 7 7 7 >>>>> 8 6 8 >>>>> >>>>> threes countpaths 7 NB. five paths begin from 7 >>>>> >>>>> ]fours =: open next threes >>>>> 0 6 8 8 >>>>> 0 8 6 6 >>>>> 1 4 0 8 >>>>> 1 4 0 6 >>>>> 1 7 1 0 >>>>> 1 7 1 1 >>>>> 1 7 1 7 >>>>> 1 7 1 6 >>>>> 1 7 7 4 >>>>> 1 7 7 7 >>>>> 1 7 7 8 >>>>> 1 7 7 1 >>>>> 1 8 6 6 >>>>> 2 0 6 6 >>>>> 2 0 8 8 >>>>> 2 2 0 8 >>>>> 2 2 0 6 >>>>> 2 2 2 6 >>>>> 2 2 2 8 >>>>> 2 2 2 0 >>>>> 2 2 2 2 >>>>> 2 2 2 5 >>>>> 4 0 6 6 >>>>> 4 0 8 8 >>>>> 6 8 6 6 >>>>> 7 1 4 6 >>>>> 7 1 4 8 >>>>> 7 1 7 4 >>>>> 7 1 7 7 >>>>> 7 1 7 8 >>>>> 7 1 7 1 >>>>> 7 1 8 8 >>>>> 7 7 1 0 >>>>> 7 7 1 1 >>>>> 7 7 1 7 >>>>> 7 7 1 6 >>>>> 7 7 7 4 >>>>> 7 7 7 7 >>>>> 7 7 7 8 >>>>> 7 7 7 1 >>>>> 8 6 8 8 >>>>> >>>>> fours countpaths 7 NB. fifteen paths from 7 >>>>> >>>>> fours -: open@:next^:2 twos >>>>> 1 >>>>> >>>>> >>>>> Sent from my iPad >>>>> >>>>> >>>>> On Feb 13, 2013, at 7:29 AM, Raul Miller <[email protected]> wrote: >>>>> >>>>>> Let's say that we have a directed, cyclic graph: >>>>>> >>>>>> graph=: 2 > ?20 20 $ 10 >>>>>> >>>>>> And, let's say that we have a starting node: >>>>>> >>>>>> start=: 19 >>>>>> >>>>>> And let us define a visitable set as a unique collection of nodes >>>>>> reachable from a starting node (in other words, a path connects them). >>>>>> >>>>>> How can we find the number of distinct visitable sets of a given size >>>>>> with a given starting node in a cyclic graph? >>>>>> >>>>>> Is it worth adjusting the graph so that node 0 is not connected >>>>>> (adding 1 to all node indices)? >>>>>> >>>>>> Thanks, >>>>>> >>>>>> -- >>>>>> 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 >> ---------------------------------------------------------------------- >> 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
