Index of /grad-school/bridge/walk_count-
Name Last modified Size Description
![[PARENTDIR]](/spicons/back.gif)
Parent Directory -
![[ ]](/spicons/unknown.gif)
Makefile 2010-02-11 12:11 739
![[TXT]](/spicons/text.gif)
ac.txt 2010-04-22 17:11 40K
ac_N_with_theta_seri..> 2010-04-23 16:46 7.5K
ac_theta_with_N_seri..> 2010-04-23 16:46 6.4K
aw_N_with_theta_seri..> 2010-04-23 16:46 7.9K
aw_theta_with_N_seri..> 2010-04-23 16:46 6.5K
bc.txt 2010-04-22 17:11 40K
bc_N_with_theta_seri..> 2010-04-23 16:46 7.5K
bc_theta_with_N_seri..> 2010-04-23 16:46 6.4K
bw_N_with_theta_seri..> 2010-04-23 16:46 7.5K
bw_theta_with_N_seri..> 2010-04-23 16:46 6.4K
count_walks 2010-04-22 11:05 15K
count_walks.c 2010-04-06 13:16 2.0K
count_walks.mk 2010-02-11 12:11 1.0K
count_walks.mki 2010-02-06 00:31 146
curvefit.aux 2010-03-26 12:08 452
curvefit.log 2010-03-26 12:08 9.3K
curvefit.out 2010-03-26 12:08 0
curvefit.tex 2010-03-26 12:08 2.6K
![[DIR]](/spicons/folder.gif)
data/ 2010-05-08 01:06 -
data_5_15/ 2010-05-08 01:06 -
datasmall/ 2010-04-22 01:28 -
files-to-send.txt 2010-04-23 17:03 448
fracs.txt 2010-04-22 18:28 438
![[ ]](/spicons/p.gif)
hv_bonds.py 2010-04-23 17:02 10K
ice/ 2010-04-16 14:12 -
logcorrectfit.py 2010-04-23 16:15 4.7K
logcorrectfit2.py 2010-04-06 21:21 4.0K
logcorrectfitw.py 2010-04-23 15:26 4.7K
logfit.py 2010-03-26 12:11 1.2K
logfits.sh 2010-04-22 17:11 169
make_raw_counts.py 2010-04-22 18:37 1.2K
objs/ 2020-07-26 21:46 -
plot3.py 2010-04-29 00:03 761
powerlawminusfit.py 2010-04-19 00:32 2.0K
sle_partition_func.tex 2010-04-07 12:44 8.1K
syms.tex 2010-03-26 12:04 7.8K
tags 2010-02-21 12:21 2.7K
tgk-lattice-effect.txt 2010-04-28 23:58 3.4K
theta.txt 2010-04-19 00:04 376
timing-info/ 2010-03-10 22:56 -
tom-shane.txt 2010-04-23 17:14 2.1K
w.txt 2010-04-22 17:11 42K
![[ ]](/spicons/layout.gif)
w_N_with_theta_serie..> 2010-04-23 16:59 71K
w_N_with_theta_serie..> 2010-04-23 16:46 11K
w_ratio_N_with_theta..> 2010-04-23 17:01 57K
w_ratio_N_with_theta..> 2010-04-23 16:46 6.1K
w_ratio_theta_with_N..> 2010-04-23 17:00 33K
w_ratio_theta_with_N..> 2010-04-23 16:46 5.1K
w_theta_fit_a1.pdf 2010-04-23 17:02 14K
w_theta_fit_a1.txt 2010-04-23 16:48 612
w_theta_fit_a3.pdf 2010-04-23 17:02 13K
w_theta_fit_a3.txt 2010-04-23 16:48 606
w_theta_fits.txt 2010-04-23 16:47 110K
w_theta_with_N_serie..> 2010-04-23 16:59 48K
w_theta_with_N_serie..> 2010-04-23 16:46 8.6K
walk_count_lib.c 2010-04-22 11:05 22K
walk_count_lib.h 2010-04-22 00:44 5.8K
================================================================
John Kerl
kerl.john.r@gmail.com
2010-02-03
================================================================
================================================================
DESCRIPTION
This is code for exhaustive enumeration of constrained walks on the 2D integer
lattice for small N (< 25 or so). This is not the same as MCMC methods which
work for much larger N, but which only sample instead of enumerating
exhaustively. This code uses a recursive backtracking algorithm to find all
walks of length <= N. Constraints are specified on the command line (see the
next section): self-avoidance constraints include none (e.g. simple random
walk), previous walk only (immediate-backstep avoidance), or full
self-avoidance; location constraints include full-plane, upper half-plane,
upper right quadrant, or Shane Passon's rational-slope constraint. Please see
walk_count_lib.h for more information.
================================================================
USAGE INSTRUCTIONS
Type "make". Then:
count_walks {constraints name} {N} [options]
or:
count_walks {constraints name} {Nmin-Nmax} [options]
Options: "kerl" or "shane" for output styles; "stdout" or "stderr" to print
individual walks.
E.g.
count_walks angle=3/7 1-12
count_walks UPSAW 1-12
count_walks UPSAW 1-5 stdout
Or: Just type "shane1.sh".
================================================================
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