From: Kaelin Colclasure
Subject: OT: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wuk8616qkj.fsf@soyuz.arslogica.com>
Let me apologize in advance for asking this question here, as it really has
nothing particularly to do with Lisp. I am happy to accept an answer in the
form of a Lisp code snippet, of course... :-)
I am totally convinced that, some years ago, I read an article in Dr. Dobb's
Journal that gave an algorithm (in C) which would generate a psuedo-random
permutation of the integers < N. That is, called ten times with N = 10, it
would return each of 0 .. 9 exactly once, but in `random' order.
It is of course trivial to write a SHUFFLE algorithm that accomplishes this
by using a vector to maintain state -- but this algorithm required no such
vector.
Does this ring a bell for anyone?
-- Kaelin
"Kaelin Colclasure" <······@everest.com> wrote in message
···················@soyuz.arslogica.com...
>
> I am totally convinced that, some years ago, I read an article in Dr.
Dobb's
> Journal that gave an algorithm (in C) which would generate a psuedo-random
> permutation of the integers < N. That is, called ten times with N = 10, it
> would return each of 0 .. 9 exactly once, but in `random' order.
>
> It is of course trivial to write a SHUFFLE algorithm that accomplishes
this
> by using a vector to maintain state -- but this algorithm required no such
> vector.
>
> Does this ring a bell for anyone?
>
There is a standard screen-dissolve trick used in graphics that does
an AND of the current value with a constant, XORs the bits together
and uses the resulting bit in an RSHIFT for the next value.
The constant depends on the size of the bit-field being considered,
it forms a cycle through every value from 1 to 2^(number of bits)-1,
0 being handled as a special case. The main problem, IIRC, is that
there is no good way of determining what constant to use, but I believe
Graphic Gems gave values for from 2 to about 32 bits. No idea if this
is what the article in question did, but if so, I'd rather use a shuffle.
Unless I was doing a dissolve, of course. :-)
Geoff
From: Kaelin Colclasure
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wuwva1lyyg.fsf@soyuz.arslogica.com>
"Geoffrey Summerhayes" <·············@hNoOtSmPAaMil.com> writes:
> "Kaelin Colclasure" <······@everest.com> wrote in message
> ···················@soyuz.arslogica.com...
> >
> > I am totally convinced that, some years ago, I read an article in Dr.
> Dobb's
> > Journal that gave an algorithm (in C) which would generate a psuedo-random
> > permutation of the integers < N. That is, called ten times with N = 10, it
> > would return each of 0 .. 9 exactly once, but in `random' order.
> >
> > It is of course trivial to write a SHUFFLE algorithm that accomplishes
> this
> > by using a vector to maintain state -- but this algorithm required no such
> > vector.
> >
> > Does this ring a bell for anyone?
> >
>
> There is a standard screen-dissolve trick used in graphics that does
> an AND of the current value with a constant, XORs the bits together
> and uses the resulting bit in an RSHIFT for the next value.
> The constant depends on the size of the bit-field being considered,
> it forms a cycle through every value from 1 to 2^(number of bits)-1,
> 0 being handled as a special case. The main problem, IIRC, is that
> there is no good way of determining what constant to use, but I believe
> Graphic Gems gave values for from 2 to about 32 bits. No idea if this
> is what the article in question did, but if so, I'd rather use a shuffle.
> Unless I was doing a dissolve, of course. :-)
Hmmm, that might have been the basic algorithm -- with the function
doing some pruning of values > N. Or maybe I'm just mis-remembering it
and N had to be a power of two. In any case, it sounds like this would
probably be suitable for the purpose I have in mind. I don't need very
random randomness, and I don't even care if the sequence generated is
always identical. (I'm generating integer id's for unique search terms
that later get inserted into a ternary tree -- thus I just need to
avoid generating ordered id's as that's a pathological case for the
tree insertion.)
Unfortunately, I don't have a copy of Graphics Gems. Any chance someone
who does could post the algorithm and the table of constants? Or a
pointer to an online description?
-- Kaelin
From: Jeff Greif
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <3AA72BE7.D09D130F@befree.com>
If the sequence can be the same each time, and N is prime, you can generate a
permutation of 0..N-1 by taking 1..N in order, multiplying each number by some
fixed number relatively prime to N, say (* 17 19) chosen to be larger than N, and
computing the result mod N. You could cycle thru a bunch of multipliers to
produce a different permutation for each of the multipliers.
Jeff
Kaelin Colclasure wrote:
> I don't need very
> random randomness, and I don't even care if the sequence generated is
> always identical. (I'm generating integer id's for unique search terms
> that later get inserted into a ternary tree -- thus I just need to
> avoid generating ordered id's as that's a pathological case for the
> tree insertion.)
>
> -- Kaelin
From: Kaelin Colclasure
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wupufsjgv2.fsf@soyuz.arslogica.com>
Jeff Greif <······@befree.com> writes:
> If the sequence can be the same each time, and N is prime, you can generate a
> permutation of 0..N-1 by taking 1..N in order, multiplying each number by some
> fixed number relatively prime to N, say (* 17 19) chosen to be larger than N, and
> computing the result mod N. You could cycle thru a bunch of multipliers to
> produce a different permutation for each of the multipliers.
>
> Jeff
Amazing! Thank you Jeff! This algorithm should do quite nicely -- although
I am still interested in the general one that didn't require carefully
chosen (prime) values of N...
-- Kaelin
A little further thought suggests this method will work even if N is not
prime, as long as the multiplier is relatively prime to it. That is,
suppose N=10. The {first 10 multiples of 37 } mod 10 are {37, 74, 111, 148,
185, 222, ... } mod 10 = {7,4,1,8,5,2,... } which should form a permutation
of 0-9. The computation is equivalent to {first 10 multiples of (37 mod
10)=7 } mod 10. For any number relatively prime to 10 (e.g. not a multiple
of 5 or 2), that number mod 10 is relatively prime to 10, and its multiples
will cycle through all the values mod 10.
Thus, another way of stating my suggested algorithm, is, take any number < N
such that gcd(N,choice) = 1. Then the first N multiples of choice mod N
form a permutation of (0..N-1).
Jeff
"Kaelin Colclasure" <······@everest.com> wrote in message
···················@soyuz.arslogica.com...
> Jeff Greif <······@befree.com> writes:
>
> > If the sequence can be the same each time, and N is prime, you can
generate a
> > permutation of 0..N-1 by taking 1..N in order, multiplying each number
by some
> > fixed number relatively prime to N, say (* 17 19) chosen to be larger
than N, and
> > computing the result mod N. You could cycle thru a bunch of multipliers
to
> > produce a different permutation for each of the multipliers.
> >
> > Jeff
>
> Amazing! Thank you Jeff! This algorithm should do quite nicely -- although
> I am still interested in the general one that didn't require carefully
> chosen (prime) values of N...
>
> -- Kaelin
"Jeff Greif" <······@spam-me-not.befree.com> writes:
> A little further thought suggests this method will work even if N is not
> prime, as long as the multiplier is relatively prime to it. That is,
> suppose N=10. The {first 10 multiples of 37 } mod 10 are {37, 74, 111, 148,
> 185, 222, ... } mod 10 = {7,4,1,8,5,2,... } which should form a permutation
> of 0-9. The computation is equivalent to {first 10 multiples of (37 mod
> 10)=7 } mod 10. For any number relatively prime to 10 (e.g. not a multiple
> of 5 or 2), that number mod 10 is relatively prime to 10, and its multiples
> will cycle through all the values mod 10.
>
> Thus, another way of stating my suggested algorithm, is, take any number < N
> such that gcd(N,choice) = 1. Then the first N multiples of choice mod N
> form a permutation of (0..N-1).
You are correct that this will generate a permutation but it will only
generate a very small fraction of them and there is no guarantee that
they will not share some common underlying structure that would be bad
when you want a "random" permutation. Just off the top of my head the
fact that all these permutations must contain a single cycle of length
N is a big red flag.
You have started down the right path though the only way I know of to
generate a combinatorial object in a truly random way is to create a
one-to-one mapping with the integers. Then once you can generate a
truly random integer[1] you just use that to map into the set of
permutations.
These are huge sets and huge numbers, for just 10 elements you need 22
bits to index every permutation. This number grows very fast with N
N Min Bits
-----------------------------------------
10 22
13 33 Can't do with 32 bit ints
21 66 Oops there go long longs
100 525
150 873
200 ? Breaks CMUCL's bignums
That number of bits is also kind of misleading since that assumes a
perfect packing of permutations into integers. When they are
generated in practice there are usually many bits lost[2] so to
generate a permutation of length 100 you need on the order of 700
random bits.
So how does one go about generating a random permutation. I would use
a simple algorithm which simulates the lexical indexing for the
permutation.
1. Put then numbers from 1 to n in a list.
2. Pick a random number i between 1 and length list.
3. Remove the ith element from the list and use it as the next element
of you permutation.
4. Until the list is empty go back to 2.
This method will generate a uniform random permutation provided you
have a good source of random bits. If you think about it, it is kind
of doing a radix lookup but leaving out the unavailable values.
In practice I don't do that though just because I don't want to go to
the trouble of coding it up and getting a sufficiently good source of
random bits. I will be making use of a similar idea later on in some
of my research and then I will go the the extra effort. Currently, I
use the following trick for mixing lists, I really don't want to call
it generating permutations but that is what it is.
(sort list-o-stuff
#'(lambda (x y) ( = 1 (random 2))))
This has a whole host of problems especially if the sort being done is
secretly stable-sort. But if you are going to be getting your
randomness from random anyway your are already a lost cause and this
is as good as anything.
I hope that helps,
-Eric "Will post for truly random bits" Dahlman
> Jeff
>
Footnotes:
[1] Do *not* use a pseudo-random number generator to generate this
integer. You will _lose_ big time. This is because most of these
generators are only look random for single numbers. Once you start
collecting tuples of numbers, like 3 or 4, they break down and become
very ununiform. To test this do a Chi^2 test of several runs of your
random number generator first binning single numbers, then pairs, then
triples etc. Very soon the statistics will show you that it doesn't
even look remotely uniform. If you are serious about this you need to
use something like LavaRand (sp?) or a radioactive decay number
generator.
[2] Bits are lost where you need to make a selection from a set which
does not contain 2^k elements. You have to use a k large enough to
hold the whole set which cause you leak fractional bits at each
selection.
From: Bernhard Pfahringer
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <98hlbb$4s8$1@hummel.cs.waikato.ac.nz>
In article <···············@sibelius.cs.colostate.edu>,
eric dahlman <·······@cs.colostate.edu> wrote:
>
>So how does one go about generating a random permutation. I would use
>a simple algorithm which simulates the lexical indexing for the
>permutation.
>
>1. Put then numbers from 1 to n in a list.
>2. Pick a random number i between 1 and length list.
>3. Remove the ith element from the list and use it as the next element
> of you permutation.
>4. Until the list is empty go back to 2.
>
Here's a reasonably simple and efficient implementation of the above idea:
(defun shuffle-list (list)
(loop with v = (coerce list 'simple-vector)
for i from (length list) downto 1
as j = (random i)
collect (prog1 (svref v j)
(setf (svref v j) (svref v (1- i))))))
It is linear, most importantly it makes only a linear number of calls to the
random number generator (the most expensive part of computation here).
Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
--------------------------------------------------------------------------
From: Kaelin Colclasure
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wu7l1uipbr.fsf@soyuz.arslogica.com>
As the OP, I thought I'd follow-up with the results I got from
experimenting with Jeff's suggestion. The algorithm I've settled on
couldn't be simpler:
(defparameter *id-seq* 0)
(defconstant id-range 1000003) ;; prime
(defconstant id-multiplier 2147483647) ;; prime
(defun gen-id ()
(mod (* (incf *id-seq*) id-multiplier) id-range))
Here some sample output:
CL-USER(5): (gen-id)
477206
CL-USER(6): (gen-id)
954412
CL-USER(7): (gen-id)
431615
CL-USER(8): (gen-id)
908821
CL-USER(9): (gen-id)
386024
Experimentation demonstrates that this will in fact generate a permutation
of the integers between 1 .. 1000002. It's certainly not random -- but it
*is* erratic enough to improve the ordering of the ternary tree that the
id's are inserted into dramatically. Search performance on a test data
set was improved by a few orders of magnitude... :-)
Thanks to all who responded.
-- Kaelin
From: Andreas Eder
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <m3g0gi18sm.fsf@elgin.eder.de>
Kaelin Colclasure <······@everest.com> writes:
> As the OP, I thought I'd follow-up with the results I got from
> experimenting with Jeff's suggestion. The algorithm I've settled on
> couldn't be simpler:
>
> (defparameter *id-seq* 0)
> (defconstant id-range 1000003) ;; prime
> (defconstant id-multiplier 2147483647) ;; prime
>
> (defun gen-id ()
> (mod (* (incf *id-seq*) id-multiplier) id-range))
>
> Experimentation demonstrates that this will in fact generate a permutation
> of the integers between 1 .. 1000002. It's certainly not random -- but it
> *is* erratic enough to improve the ordering of the ternary tree that the
> id's are inserted into dramatically. Search performance on a test data
> set was improved by a few orders of magnitude... :-)
>
A little bit of math will show you that it is indeed a
permutation. Quite a few random generators are based on a similar
principle: look up linear congruential RNGs in Knuth vol. II
Andreas
--
Wherever I lay my .emacs, there�s my $HOME.
From: Geoff Summerhayes
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <taf9rpn6f9mp96@corp.supernews.com>
"Kaelin Colclasure" <······@everest.com> wrote in message
···················@soyuz.arslogica.com...
>
> Hmmm, that might have been the basic algorithm -- with the function
> doing some pruning of values > N. Or maybe I'm just mis-remembering it
> and N had to be a power of two. In any case, it sounds like this would
> probably be suitable for the purpose I have in mind. I don't need very
> random randomness, and I don't even care if the sequence generated is
> always identical. (I'm generating integer id's for unique search terms
> that later get inserted into a ternary tree -- thus I just need to
> avoid generating ordered id's as that's a pathological case for the
> tree insertion.)
>
> Unfortunately, I don't have a copy of Graphics Gems. Any chance someone
> who does could post the algorithm and the table of constants? Or a
> pointer to an online description?
>
http://www.acm.org/pubs/tog/GraphicsGems/gems.zip
Dissolve.c contains 2 versions of the algorithm in C, I'll
e-mail you the masks sometime within the next 48 hrs.
As a start, from the errata:
the Bit Width 23 mask is listed as 0x00400000, it should be
0x00420000.
The code will take some rework, it's specifically coded
for a dissolve.
Geoff
From: Kaelin Colclasure
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wusnkojhw7.fsf@soyuz.arslogica.com>
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> > Unfortunately, I don't have a copy of Graphics Gems. Any chance someone
> > who does could post the algorithm and the table of constants? Or a
> > pointer to an online description?
> >
>
> http://www.acm.org/pubs/tog/GraphicsGems/gems.zip
>
> Dissolve.c contains 2 versions of the algorithm in C, I'll
> e-mail you the masks sometime within the next 48 hrs.
>
> As a start, from the errata:
>
> the Bit Width 23 mask is listed as 0x00400000, it should be
> 0x00420000.
>
> The code will take some rework, it's specifically coded
> for a dissolve.
Thanks Geoff! I'll have a look and see what I can come up with.
-- Kaelin
"Geoff Summerhayes" wrote in message
···················@corp.supernews.com...
>
> The code will take some rework, it's specifically coded
> for a dissolve.
>
FWIW, I did a straight port of the second C screen dissolve
program in Graphics Gems to Lisp. The only real changes
were to add the error check and change the direct calling
of a copy routine to a funcall. Feel free to pick it apart,
I spent the minimum amount of effort to get it working.
You can test it with something along the lines of:
(speckle 10 5 (lambda(x y)(format t "~A ~A~%" x y)))
Geoff
(defconstant masks (vector nil nil #X03 #X06 #X0c #X14 #X30
#X60 #Xb8 #X0110 #X0240 #X0500
#X0ca0 #X1b00 #X3500 #X6000 #Xb400
#X00012000 #X00020400 #X00072000
#X00090000 #X00140000 #X00300000
#X00420000 #X00d80000 #X01200000
#X03880000 #X07200000 #X09000000
#X14000000 #X32800000 #X48000000
#Xa3000000))
(defun bitwidth(x)
(let ((y 0))
(declare (fixnum x y))
(loop
until (= 0 x)
counting y
do (setf x (ash x -1)))))
(defun speckle(width height fn)
(let* ((bheight (bitwidth height))
(bwidth (bitwidth width))
(regwidth (+ bheight bwidth))
(rowshift (- bwidth))
(colmask (- (ash 1 bwidth) 1)))
(unless (< 1 regwidth 33)
(error "~A ~A values force out of range error" width height))
(let ((mask (svref masks regwidth))
(element 1))
(loop
(let ((row (ash element rowshift))
(col (boole boole-and element colmask)))
(when (and (< row height)(< col width))
(funcall fn col row))
(if (oddp element)
(setf element (boole boole-xor mask (ash element -1)))
(setf element (ash element -1)))
(when (= element 1)
(funcall fn 0 0)
(return-from speckle)))))))
From: Marco Antoniotti
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <y6cae6r3u62.fsf@octagon.mrl.nyu.edu>
"Geoffrey Summerhayes" <·············@hNoOtSmPAaMil.com> writes:
> "Geoff Summerhayes" wrote in message
> ···················@corp.supernews.com...
> >
> > The code will take some rework, it's specifically coded
> > for a dissolve.
> >
>
> FWIW, I did a straight port of the second C screen dissolve
> program in Graphics Gems to Lisp. The only real changes
> were to add the error check and change the direct calling
> of a copy routine to a funcall. Feel free to pick it apart,
> I spent the minimum amount of effort to get it working.
> You can test it with something along the lines of:
> (speckle 10 5 (lambda(x y)(format t "~A ~A~%" x y)))
>
> Geoff
>
> (defconstant masks (vector nil nil #X03 #X06 #X0c #X14 #X30
> #X60 #Xb8 #X0110 #X0240 #X0500
> #X0ca0 #X1b00 #X3500 #X6000 #Xb400
> #X00012000 #X00020400 #X00072000
> #X00090000 #X00140000 #X00300000
> #X00420000 #X00d80000 #X01200000
> #X03880000 #X07200000 #X09000000
> #X14000000 #X32800000 #X48000000
> #Xa3000000))
>
> (defun bitwidth(x)
> (let ((y 0))
> (declare (fixnum x y))
> (loop
> until (= 0 x)
> counting y
> do (setf x (ash x -1)))))
Isn't it better
(defun bitwidth (x)
(declare (fixnum x))
(integer-length x))
?
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
Like DNA, such a language [Lisp] does not go out of style.
Paul Graham, ANSI Common Lisp
From: Geoff Summerhayes
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <tapsvvp8io5n13@corp.supernews.com>
"Marco Antoniotti" <·······@cs.nyu.edu> wrote in message
····················@octagon.mrl.nyu.edu...
>
> "Geoffrey Summerhayes" <·············@hNoOtSmPAaMil.com> writes:
>
> >
> > (defun bitwidth(x)
> > (let ((y 0))
> > (declare (fixnum x y))
> > (loop
> > until (= 0 x)
> > counting y
> > do (setf x (ash x -1)))))
>
> Isn't it better
>
> (defun bitwidth (x)
> (declare (fixnum x))
> (integer-length x))
>
Arrgh! Yes, of course it would. Forest and trees, again. :-)
Geoff
Kaelin Colclasure <······@everest.com> wrote:
>Let me apologize in advance for asking this question here, as it really has
>nothing particularly to do with Lisp. I am happy to accept an answer in the
>form of a Lisp code snippet, of course... :-)
>
>I am totally convinced that, some years ago, I read an article in Dr. Dobb's
>Journal that gave an algorithm (in C) which would generate a psuedo-random
>permutation of the integers < N. That is, called ten times with N = 10, it
>would return each of 0 .. 9 exactly once, but in `random' order.
>
>It is of course trivial to write a SHUFFLE algorithm that accomplishes this
>by using a vector to maintain state -- but this algorithm required no such
>vector.
>
>Does this ring a bell for anyone?
>
Something like this maybe. first shuffle the whole set of data and then go
through from the first one to the last one
If your data are stored in an vector
- pick randomly an index value, I
- get the element for this index, E
- copy the last vector element in I slot
- store E in the last vector slot
continue recursively with the same vector minus the last element
--
Francis Leboutte www.algo.be +32-(0)4.388.39.19
From: Jeff Sandys
Subject: Re: OT: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <3AA7C066.2EAE38EF@asme.org>
Kaelin Colclasure wrote:
>
> It is of course trivial to write a SHUFFLE algorithm that accomplishes this
> by using a vector to maintain state -- but this algorithm required no such
> vector.
This is a Logo algorithm to shuffle a vector, written by Brian Harvey.
It seems that keeping track of the shuffled items makes the algorithm
you requested impossible.
to shuffle :deck
output shuffler (count :deck) :deck
end
to shuffler :len :deck
local [choice card]
if :len=0 [output :deck]
make "choice random :len
make "card item :choice :deck
setitem :choice :deck (item :len-1 :deck)
setitem :len-1 :deck :card
output shuffler :len-1 :deck
end
Same code transilated to Lisp:
(defun shuffle (deck)
(shuffler (length deck) deck))
(defun shuffler (len deck)
(cond ((= len 0) deck)
(t (let* ((choice (random len))
(card (elt deck choice)))
(setf (elt deck choice) (elt deck (1- len)))
(setf (elt deck (1- len)) card)
(shuffler (1- len) deck)))))
You may be interested in this web site on shuffling:
http://paradisepoker.com/rng.html
http://paradisepoker.com/shuffling.html
Thanks,
Jeff Sandys
"Kaelin Colclasure" <······@everest.com> wrote in message
···················@soyuz.arslogica.com...
> Let me apologize in advance for asking this question here, as it really
has
> nothing particularly to do with Lisp. I am happy to accept an answer in
the
> form of a Lisp code snippet, of course... :-)
>
> I am totally convinced that, some years ago, I read an article in Dr.
Dobb's
> Journal that gave an algorithm (in C) which would generate a psuedo-random
> permutation of the integers < N. That is, called ten times with N = 10, it
> would return each of 0 .. 9 exactly once, but in `random' order.
if i have understood the problem correctly....
(defun scrambled-counting (n)
(let ((eggs '()))
(loop until (= (length eggs) n)
for next = (random n)
for nudger = (up-or-down-1)
do
(when (member next eggs)
(loop until (not (member next eggs))
do (setf next (funcall nudger next))))
(when (and (>= next 0) (< next n))
(push next eggs)))
eggs))
(defun up-or-down-1()
(if (> 50 (random 100))
'1+
'1-))
all comments, criticism and kvetching is welcome...
Coby
From: Kaelin Colclasure
Subject: Re: Function to generate a psuedo-random permutation of integers < N
Date:
Message-ID: <wuvgpkjhzc.fsf@soyuz.arslogica.com>
"Coby Beck" <····@memetrics.com> writes:
> "Kaelin Colclasure" <······@everest.com> wrote in message
> ···················@soyuz.arslogica.com...
> > Let me apologize in advance for asking this question here, as it really
> has
> > nothing particularly to do with Lisp. I am happy to accept an answer in
> the
> > form of a Lisp code snippet, of course... :-)
> >
> > I am totally convinced that, some years ago, I read an article in Dr.
> Dobb's
> > Journal that gave an algorithm (in C) which would generate a psuedo-random
> > permutation of the integers < N. That is, called ten times with N = 10, it
> > would return each of 0 .. 9 exactly once, but in `random' order.
>
> if i have understood the problem correctly....
Hmmm, not quite. Although the part of my post you snipped only explicitly
disallowed using a vector to hold the state of the generator, using a list
is out of the question too. Consider the space requirements when N=2^32...
Also, the SHUFFLE algorithm computes a permutation of a given size with
a constant number of operations. SCRAMBLED-COUNTING might never terminate
for larger values of N.
> (defun scrambled-counting (n)
> (let ((eggs '()))
> (loop until (= (length eggs) n)
> for next = (random n)
> for nudger = (up-or-down-1)
> do
> (when (member next eggs)
> (loop until (not (member next eggs))
> do (setf next (funcall nudger next))))
> (when (and (>= next 0) (< next n))
> (push next eggs)))
> eggs))
>
> (defun up-or-down-1()
> (if (> 50 (random 100))
> '1+
> '1-))
>
> all comments, criticism and kvetching is welcome...
>
> Coby