Index of /grad-school/bridge/walk_count_v1
Name Last modified Size Description
![[PARENTDIR]](/spicons/back.gif)
Parent Directory -
![[ ]](/spicons/unknown.gif)
Makefile 2010-02-11 12:45 555
count_HPEs 2010-02-03 17:06 30
count_SAWs 2010-02-03 17:06 30
count_SRWs 2010-02-03 17:06 30
count_UPSAWs 2010-02-03 17:06 32
count_tris 2010-02-03 17:06 30
count_walks 2010-02-03 21:32 13K
![[TXT]](/spicons/text.gif)
count_walks.c 2010-02-03 20:02 1.6K
count_walks.mk 2010-02-11 12:45 1.0K
count_walks.mki 2010-02-03 17:06 142
![[DIR]](/spicons/folder.gif)
ice/ 2010-02-03 17:46 -
objs/ 2020-07-26 21:46 -
regress.sh 2010-02-03 20:02 440
regress_curr.txt 2010-02-03 20:02 3.1K
regress_orig.txt 2010-02-03 17:37 2.7K
shane1.sh 2010-02-03 17:06 211
shane1.txt 2010-02-03 17:06 3.3K
shane2.txt 2010-02-03 17:23 3.3K
tags 2010-02-03 17:06 3.0K
time-saws.txt 2010-02-03 17:06 836
time_upsaws.sh 2010-02-03 17:38 69
todo.txt 2010-02-11 12:45 654
upsaw-times.txt 2010-02-03 17:39 269
walk_count.c 2010-02-03 20:02 18K
walk_count.h 2010-02-03 20:02 5.6K
================================================================
John Kerl
kerl.john.r@gmail.com
2010-02-03
================================================================
================================================================
XXX
================================================================
XXX
xxx exhaustive search for small N; not the same as MCMC methods for large N.
================================================================
TEST CASES
Here are test cases I have run. There are three self-avoidance constraints
and three location-conditioning constraints (besides Passon's slope
constraints). Some combinations of those have well-known names:
* No self-avoidance in the full plane: this is a simple random walk
("SRW"). There are 4^N such walks, since at each step one can choose any
of the four directions.
* No self-avoidance in the upper half-plane: this is the half-plane
excursion (HPE).
* No self-avoidance in the upper right quadrant: this shows up in Sloane's
integer sequences.
* Avoiding only immediate backsteps in the full plane: there are 3^N such
walks, since at each step one can choose from any of the three
non-back-step directions.
* Avoiding only immediate backsteps in the upper half-plane or upper right
quadrant: I haven't found references to these anywhere.
* Self-avoiding walk in the full plane: "SAW". Counts are available on the
web, including via Sloane.
* Self-avoiding walk in the upper half-plane: "UPSAW". Counts are
available on the web, including via Sloane.
* Self-avoiding walk in the upper right quadrant: I don't know of a short
name for these. Counts are available via Sloane.
Neil Sloane's sequences may be found at
http://www.research.att.com/~njas/sequences,
and/or Google for OEIS (On-line Encyclopedia of Integer Sequences).
The following table summarizes my results, using this program, for these
known-value test cases. Counts are shown for N=0,1,2,3,... . What I am
showing here is the correctness of my code: for each case where there were
results to compare to, I indeed obtained the correct results.
Slf-avd Loc Desc. Verif. Count
------- --- ---- ------ -----
None FP SRW Yes 4^N 1,4,16,64,256,1024,4096,16384,65536
None UHP HPE Yes Sloane A001700 1,1,3,10,35,126,462,1716,6435,24310
None URQ ??? Yes Sloane A005566 1,2,6,18,60,200,700,2450,8820,31752
Prev. FP ??? Yes 4*3^(N-1) 1,4,12,36,108,324,972,2916,8748,26244
Prev. UHP ??? N/A ??? 1,1,3,7,19,53,147,411,1163,3313,9475
Prev. URQ ??? N/A ??? 1,2,4,10,26,66,174,462,1256,3410,9410
Full FP SAW Yes Sloane A001411 1,4,12,36,100,284,780,2172,5916
Full UHP UPSAW Yes Sloane A116903 1,1,3,7,19,49,131,339,899,2345,6199
Full URQ ??? Yes Sloane A038373 1,2,4,10,24060,146,366,912,2302,5800