Re: Hash Table for self avoiding random walks

*To*: mathgroup at smc.vnet.net*Subject*: [mg88499] Re: Hash Table for self avoiding random walks*From*: Szabolcs Horvát <szhorvat at gmail.com>*Date*: Tue, 6 May 2008 06:45:43 -0400 (EDT)*Organization*: University of Bergen*References*: <fvmn1l$8jn$1@smc.vnet.net>

jwmerrill at gmail.com wrote: > Here's my current best effort: > > neighborhood[n_] := > With[{seed = ReplacePart[ConstantArray[0, n], 1 -> 1]}, > Join[Permutations[seed], Permutations[-seed]]] > > availableSteps[{points_, visitedFunction_}] := > With[{steps = (Last[points] + #) & /@ > neighborhood[Dimensions[points][[2]]]}, > Select[steps, visitedFunction[#] =!= True &]] > > takeStep[{points_, visitedFunction_}] := > With[{newStep = > RandomChoice[availableSteps[{points, visitedFunction}]]}, > visitedFunction[Last[points]] = True; > {Append[points, newStep], visitedFunction}] > > Clear[trail]; > {points, trail} = > NestWhile[ > takeStep, {{{0, 0, 0}}, trail}, (Length[availableSteps[#]] > 0) &]; > > The part that I really don't like is the Clear[trail] part. > Your code looks good to me. You can use Module[] to localize 'trail', this way it won't be necessary to use Clear[]. Here's a slight modification that runs ~4x faster on my machine: neighbourhood[n_] := neighbourhood[n] = With[{seed = ReplacePart[ConstantArray[0, n], 1 -> 1]}, Join[Permutations[seed], Permutations[-seed]]] step[visited_][pt_] := With[ {steps = Select[(pt + #) & /@ neighbourhood@Length[pt], ! ValueQ[visited[#]] &]}, If[steps =!= {}, With[{next = RandomChoice[steps]}, visited[next] = True; next ], Null] ] Module[{trail}, Most@NestWhileList[step[trail], {0, 0, 0}, # =!= Null &] I've thrown this together quickly, so it's a bit messy ... sorry about that (especially about merging takeStep and availableSteps, which serves no purpose in this case). The two main optimizations are caching the result of neighbourhood[], and using NestWhileList instead of NestWhile + Append. I have not timed the parts of the function separately, but I suspect that the speedup is due to the latter change. I hope this helps, Szabolcs