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

```

• Prev by Date: graph plot
• Next by Date: Re: orthonormal eigenvectors
• Previous by thread: Re: Hash Table for self avoiding random walks
• Next by thread: Re: Hash Table for self avoiding random walks