--Apple-Mail-10--42713177
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed


On Jun 11, 2006, at 2:22 PM, Phil Keller wrote:
>
> I have an application that I need to generate a random number
> sequence for.  Not just a random number, I know how to do that,
> but an entire pseudo random sequence.

You want a "shuffle" algorithm.  With a similar problem some time
ago, I came up with this framework (in C):

The enclosed code in shuffle_lib.c will return a shuffled sequence of 
any
number of items up to 65535, using only 6 bytes or less of storage.  A
pseudo-random number generator (PRNG) can be used to produce a 
non-repeating
sequence of numbers, but the usual implementation will generate only a
sequence of length 2^N-1 (for an N bit number.)  That's not a problem, 
you
can just filter out all the numbers that are outside the range of 
interest.
The other problem with a PRN is that the sequence itself repeats; 12 
always
follows 232, or whatever.  Since our PRNG is generating a larger range 
than
we want anyway, this can be fixed by permuting the number somehow before
filtering, using a separate permutation constant.  This means that our 
final
algorithm is something like:

     shufflednum(max) = filter(max, permute(prng(randreg), 
permuteconst));

The code example enclosed uses a standard shift-with-xor-feedback 
scheme for
the PRNG, simple subtraction for the permutation, and a test against the
maximum as the filter, making it quite fast.  (however, it needs to be 
fast
if the number of items to be shuffled is much smaller than the size of 
the
PRNG.  to get 10 items with a 16 bit PRN, you may end up filtering out 
65525
numbers.  This can be optimized by using a shorter PRN, of course.)  
Note
that by changing the PRNG seed, you change the starting position of the
shuffled list, but not the list itself, while changing the permutation
constant results in dramatically different sequences.

Enclosed files:

shuffle_lib.c: library functions in hopefully machine-independent C code
shuffle_test.c: demonstration program, written for unix, tested on 
Solaris
shuffle_log.c: sample run, demonstrating effects of seed vs permutation
                constant changes



--Apple-Mail-10--42713177
Content-Transfer-Encoding: base64
Content-Type: application/zip; x-mac-type=5A495020; x-unix-mode=0755;
	x-mac-creator=53495421; name="Shuffle.zip"
Content-Disposition: attachment;
	filename=Shuffle.zip

UEsDBBQAAAAIACy2uTAnbZBSHwIAAPwFAAAPAAAAc2h1ZmZsZV9sb2cudHh0hZRNj5swEIbv/hWj
lXJjqW0wJJH20ktP/VDbW7WqWDABLbFTMO3uv69nEGZTleBIr8aeseN5ZvC3sm8vDgZX9E5XYA18
HzV8LF5BKhDZUSVHpUBynrLRtC9iB6eyhKEZ67rTP50eXLxMu/bJz+7tlZ/2yR3E765W2Y+hOF86
Df1oHhlr7J9zYV4jsHU9aBfBoHXFJAcBInjhwd8kAoDPFOSnYgpEi4EfAiVByXGWoSgUjiJRUhTy
HjBujxYKpCi0ljFcpGMkCp1AR3PG7lfG1vAZl01hTq05gWs0fPn66cN0eVrWA0xVQP/FDq1rrYng
aXRgrPOBv0ZtSh0DvLeuYT627ToorXFFa0D4pHOfr8/W5xrH8eNNohyRbiHFMKKxCuOK+BZxtop8
Ybo1tphedH8eXYHoEI3naRyc2t8ebgHnsWygauta99osRG82H7/dffyf9ssnXphfgJaEfiOHCgR4
6DdCRTtSorKgkgEnbZE3UW2hqm0PhbEeVA/6xX99Opq/VI/nrtLlsycAZdFXw53voVUySvqrJCmo
LN+/xaPkWzwUMwOaYjE5iSJCCyy9ckCHCqBQJErC0bGf+UqBU2onFSgnRJ4CaXNyRVSGZkvC15/S
33FcSxiqnAuT0oEC92GM4mjlcyHSdK6LpLhsanNUnCqGHonmAS0qN1l0DN1hv17FrbFWEQ7+Ry9t
smPD9KZX1uj/POjqKLLpQf8LUEsDBBQAAAAIABKwNjLj4+zvdgQAANYIAAALAAAAc2h1ZmZsZS50
eHRdVU2P2zYQvfNXDHKJjcpGdhebQ4Ie0iQIeugiaHJuQUsjiV2JVDjketVf3zeUtI5rwF8i+ebN
mzfD3+lshX5kl5gaJ3aagvOJGzr37GmcyfOZ7g9YeqQ/vt7Rx09U99Z3HOkc8tD418m8kj637cCv
aDcNdiYJvhMKvmZiW/fkPEXrmzBSiA3HPQk/cbSDAE0AE1NPoTWAX4/uxM4V3bx588v6YEI4RG5D
VETdTalnuleA4/G4J/pAJ5cUJTKY1MkFT3XwT87XSGZk7LepHJpi6KIdR46CjDUBevThTD3eKZjR
In+8ydKSFo4PThR740199k3E84Vc2Tu6OgYETDEMA0dz7oMw4o4hziqxhj3Z0zBTm4eBToxcWPnM
ZJsGWEptnO6o4TpApCPRbzmZOWRqgnJ8+Pz5E/jRCz/JEMIu3P7J+MAigjS55p+4G+EfmSHC0Zjv
CIGfQxDE0yigvm38e3CnY01nB3KRU45XAmwgKoL1s/F5PHHUf/DNKJQnjf72/v7uvqIszncoP3J9
S6c5sRDqNrBI0TCFaDtGfh/MJJybcFjNsYJ27CFywpHd1z8fvuypth56AZab6xx98IfIE9uEgOYn
jiuUVHTKWnQ9nFE3N04Djwz91B8l2S0cL4TtzzDg7Dt48/avh8MN7dR9oPKgTlsjqPO+w1ivBWQS
2VJlhKgIhTMgvlSmdUNSuTK2ICQIbQwXW9rIuiiu4bIYtcGKuh7nWNKx1C5gLW4hwD5p/aERObnY
+4W/S8JDS4tA8p5ubhH8bGcxLSwazkK3d7eVluaMs/xUPPfNldRzVNwvAF70KQqr2WxE5y/8NKQ3
Z4a7fVJXALvCQ5xZKoa0n1Gy06ztO+YCcUkdzTMyem5tBbNohD2bgSxSmayWZj1vt6aWhIgg+11j
jWz9kr7SRkxvB2OHLkToMyKDEij1Cjm4R35nDOG1WRtkdqN93tOva5X0X7VG5N0UfbeLVtu92788
Lhz2+/elpZZO4mcLc136S+0qmkPCYRsbBHRtOmjRDs8hHlrm5mTrR5K6hyV1tBmIU2SvSIpT0eKn
FG0ZZroBWV5pURGwEQMdhgJ0GAr4xh6DFNyYR7Kif9fEKoyOR1XBpXXet1ZUxh2qoOWvdMWDl2ib
nZZ145ZRe93x647LgNBC6DyS0er4K95Y7Oj+VScXWpob4uFoxwnjfYHajHzztjQWNpXuAdsZajY6
W168oV2iY+b23qwNVGxwsVyYkhsRUm138VEfIs4XaOVSwyjC2rsPIbFR72D7cq+tJl3sLxCjkFnW
SnNqRWPx8hTEaRm29K6uizJ6dCjoUnmyNmSFdnMDv0T7f1HNZnBC4+chlfulwYWF1Rrizri02hZT
ATu2XhcM98+b8VqgC1x+NdjfEb6ijXr9+GKogtuHifU+mqF2jRbhg/MNBgY+AP+xWPsFSG2mSA2P
SjEWutt1irTQcIkXo2bv0ER6AISw6VvA5HBy4RQ6RZKlZ2L21QW1aMtIsU6yXLrAeJIrjej6tUm2
lknMf1BLAwQUAAAACAAstrkwUapEBz8FAAAMDQAADQAAAHNodWZmbGVfbGliLmOFVllvGzcQfo5+
xUAPheRKsuQcCOK4QFsUrYHAKZIUQV9qULuzEmEuueUhWQ3y3ztDcnd1Gd4HGyLn4jffHJcXA7gA
tw5VpfBeyeWs4INfTbOzcrX2cDWfX03pzytY7uAXqRR8RecriaokQZb9WYNQK2OlX9dQGQuNNWUo
pF6BACt0aWpw+G9AXSBUln7dgfRYOwiOhWqpZS1UjMMbK1YIo5dXsJTejQG+rLHX3rJ/bTxYbFD4
ZGYCy+ChEBqWmC+wZGtmg1aQwnKXPXm2JWo2iKUDCg1MVTn0bkbyl4NBQkNqj1YL1YbDj2LdFqb+
uSTNATo6snQdmsY4LMEbDmXxJr4BUBTra3hAbMgj4A7BaNiZYKEwdSMV2uTdeeFlAUE7udJYkjdj
fQTQ4uoa4nfJuZIVA7CSjsKEPz/dxec8baFBWwe+Mfq+MJqEtL+Optpf/MB9MbbVgtE4DKVJaaTf
5NgHqyMcGh99vp/mPOtQLymoEUU1zqALgpEuhS2hFo+yDjWwHYV65dfwaOy0ovCXonggxKaE2NEL
Zwlk6bJrx76zo0SnBQP+5vXrl68pdeSvko9YRlKIpqHEaK92ZOSYizOAO0O5aI1l7rjocBQ9yuRs
2L5gCEpqFPY4CVuZngLtUzgt15GDpJ+StEJNdCRGOcI9qJIpEogts/HT2T9An/g02hhZjgffBkSF
Y1GNWwbvBubXg3gvKxhl9sANHY+B9PLXncPiOh5+P1H5AeaPb+dzUkuWW9lTqVf7Uv88KbZIYs+J
kdTbU7E+4l76/XtYjOHHLBvFMke6qhl8zzzu6I2pwsHYkhLjTZsXhDooLxuFGfSeLRiILS5xTQCT
WrGVlvpHghPYIiVKWCmWajeG0pDS4t0CamIj6VLLiaSqpHWezERyeBIiC1SQJf3zRM3PYemtKGI5
bo19cKSgybhw9JPpI8pS8u2EiTdhQxRH5hu1ISeXUpEARj4/1xso4qMbqZvgI9V6VEfxEKZnW8qY
wWa0u++577kvz5cvDJZRymwZvYowZr+OW24EEh9Tu1Y72Eh6tsLUwStRkIBhGTJz2rwZl+577nvu
6+dHP01prvn0Bs5pjLUFy8XSp8m0P1fK3Ij6VjHL6reMu3t3kj2r72Pvn0Yz7E/S2NoIFbqhddh7
2Fj+SPzMbCBTvTqdeEvIE+77kjmo0d8m8NglL1I/ZFo7CiMGS3VSN2rHfPVbQwA0giLIo5f4/YfZ
4gYTcaFYC72KtaFVhKR/Wi12RD9HtUmGu97NfZnmfxkaJQvh6TeZ946NUSCpCjphcjeK4tJNqN3w
7E0esfPXjdEJDBfDuGdEW1Sy3O7ZlawqtMiYKcEByDgEOydpC/H7XG3T2VtTW7Fz1Pi7TSQ2f777
GHxKsabYSTdn/nLAHf+AUTB6ggWTsxlta7hvoJ1C6piXF/FfjOFoUuV9i/LULnUI/6E13VsPloav
tx8+tKaCpu5Kb7E18bGQtgg18T7lAn7TLlhMGdxii8pabGjSJpVs5lBzyOVSSicyvDGU2WyWhS+7
aXICQRp/gxdnLtr5cq6l0fXpcexyx5XOm9CItpsxH/4uN6j3lxRTtYtqI4sHatN7e0m7lAzZRBSb
DdnIX7xTnl+uRFpKlsLJgjRSqmJKuKl0RE2z5eOnL7cf7z7n6nxyZAmeOw+yicWfqys2WBPYDqtb
Lpi2IX1Kq1gU72ohibDsfDZjOKaLceqLh4w9gI2HiufN8Pxak2s/rTQ8S78NXsSj/eTg6HBPGo3H
eauB7VoqGm5Z5aeb6OlgVYhXMa3/A1BLAwQUAAAACAAstrkwMotUgp0CAABsBQAADgAAAHNodWZm
bGVfdGVzdC5jhVNRb9MwEH6Of8WpaFPadVs7tqeuSMADICF4AImXSZUTXxqL2C62s65M++/cOUm7
DiEsq6rj7/vu7rvz5UTABL7VbVU1uIoY4kXJX967zc7rdR3haja7Oqefayh28E43DfwgVKWxUQRk
7FsLslk7r2NtoHIeNt6pttR2DRK8tMoZCPirRVsiVJ5OX0BHNAHawCCjrTayYakQnZdrhPz1FRQ6
hjHA9xoP7C3Hty6Cxw3K2MlMoWgjlNJCgf0FKlZz9+glEYpdHymyljQsiCoApQauqgLGcNHVQtF0
ANoSFBpnQ/Qyame5pLWXhhQoKj6U6EsdMCTFRhde+h1oC6EzMnl4KYR4pW3ZtArhNkSl3UX9Rgh8
iOgttDbotUVFHOfjwFxZus61jWDkw3gxgO+dVnsI2RXzYzrlZ1dc1JSyoBN608aU+arkKqSNJCZE
0uEuQz4WjwJoMV4vsizjw+UEPju3gdK1lgJTEXtM7bZG2t1iD/zotsBfwLamQE9euCHFnveyRm/V
gT6KZPWon4+kcRSvb8yUW3VgdY3jIUvOr9EiNcglYmIqB48io6nOYEIyGxoMJaNkxnFHCUCcbOMp
VpWP+uqmR2Hv7IhcywKNFkFOFKQ9msLpHn464E+ZwGhdQd5fw+0SZmORci88yp8Lsc/tEzVRy0b/
Rq5kb5zBspZWB9Pnd9RzDjFkOH6m9QFjmuVUTJLz/GBCpJnvnSXWEEMNDXthwZ0d0l5SlVPK+WuK
1B85OP9lV6ZE7dZfvg02sOG5Xs4WoOF2gNHh7GwMjx3dWxI8HvweRwIJMaR2ckOuM364YJM1nMD8
BpZLmF8nzWeVjAbgk8hov7g4HM//sf637mwnlULAttbUunxOH56EMFLb/fNKjy3vLv4AUEsBAhQD
FAAAAAgAErA2MuPj7O92BAAA1ggAAAsAAAAAAAAAAAAAACSBTAIAAHNodWZmbGUudHh0UEsBAhQD
FAAAAAgALLa5MFGqRAc/BQAADA0AAA0AAAAAAAAAAAAAACSB6wYAAHNodWZmbGVfbGliLmNQSwEC
FAMUAAAACAAstrkwJ22QUh8CAAD8BQAADwAAAAAAAAAAAAAAJIEAAAAAc2h1ZmZsZV9sb2cudHh0
UEsBAhQDFAAAAAgALLa5MDKLVIKdAgAAbAUAAA4AAAAAAAAAAAAAACSBVQwAAHNodWZmbGVfdGVz
dC5jUEsFBgAAAAAEAAQA7QAAAB4PAAAAAA==

--Apple-Mail-10--42713177
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

--Apple-Mail-10--42713177--