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
