Hash Table for self avoiding random walks

*To*: mathgroup at smc.vnet.net*Subject*: [mg88453] Hash Table for self avoiding random walks*From*: "jwmerrill at gmail.com" <jwmerrill at gmail.com>*Date*: Mon, 5 May 2008 06:17:32 -0400 (EDT)

Executive Summary: Can I make a bunch of things that work like hash tables without polluting the global scope? Long winded Version: I've been playing around with self avoiding random walks. Generating them efficiently requires a fast way of checking whether a given step will intersect the set of previous steps, which is generally a sparse subset of the underlying lattice. Using a list of the previous steps isn't so great because searching it for collisions is order the size of the list. Using an array isn't so great because it has predefined boundaries and because, as the dimensionality increases, the size of the array goes like (side length)^dimensions. I think the ideal data structure is a hash table. It takes constant time to add new elements and constant time to check if a trial step collides with a previous step, and there are no predefined boundaries. But it seems Mathematica doesn't have a true hash table. SparseArray doesn't qualify because it wraps negative values and complains if you look for something outside the boundaries. Dispatch doesn't qualify because (as far as I know) there's no way to add new rules to an already created DispatchTables. Googling <Mathematica Data Structures> led me to a nice article by Daniel Lichtblau: http://library.wolfram.com/infocenter/Conferences/321/ , which shows how downvalues can be used in a similar way to hash tables. The article is from 1999, though, and I'm wondering if it's still the state of the art. The idea is simple. If I have a walk that took steps {{1,1},{1,2}, {2,2}} then I make a function h: h[{1,1}] = True; h[{1,2}] = True; h[{2,2}] = True; My primary complaint with this technique is that it seems to require giving your hash table a name with global scope. What if I want to make 100 different walks? Do I have to give them all separate names? I guess I could do something like h[10][1,1] = True;, but then I always have to keep track of which walk I'm working on. I'd rather just be able to let them all be anonymous and stick them in a list. Any ideas? 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. As an aside, although there is no documentation for HashTable, doing FullForm[Dispatch[Table[n -> 1, {n, 4}]]] gives Dispatch[List[Rule[1,1],Rule[2,1],Rule[3,1],Rule[4,1]],List[HashTable[1,4,1,List[List[1,2,3],List[],List[4]]]]] Is the feature set I want just hiding? Regards, JM

**Follow-Ups**:**Re: Hash Table for self avoiding random walks***From:*"W_Craig Carter" <ccarter@mit.edu>

**Re: Hash Table for self avoiding random walks***From:*"Jason Merrill" <jwmerrill@gmail.com>

**Want a general method to extract cases resulting from Reduce**

**Re: Re: function to check if array is empty**

**Re: Want a general method to extract cases resulting from Reduce**

**Re: Hash Table for self avoiding random walks**