the most stupid randomization problem

[David McFarlane]

Hmm, interesting puzzle, not your typical "randomize without consecutive 
repeats" problem.  First let's make sure that I have it right.  Your 
stimuli consist of single digits from 0 to 9, and you want to present 
these in a somewhat random trial sequence such that each stimulus 
follows every other stimulus (except itself) exactly once.  Do I have 
that right so far?  If so, then I believe you will need 91 trials to do 
this, and the final trial will always be the same as the first.  Also, 
although PST's bogosort- (look that up on Wikipedia) style algorithm in 
their NoRepeat.es example may work in simple cases, it would almost 
certainly fail to produce a solution in any reasonable time for your 
criteria.  And you would still need to write the code to filter for your 
criteria (which are more complicated than merely no consecutive 
repeats), which would present another tough challenge.  The method I 
present here may be no easier to program, but at least it does provide a 
full solution that will run in a deterministic time frame.

Now, I like to think of these puzzles in terms of how I would do them 
manually with decks of cards or with pencil and paper.  I also like to 
reduce them to a simpler example and then scale up later.  So let's look 
at how we might arrange a sequence of simply 1, 2, and 3 following your 
criteria.

I might start by writing a list of all trial (or stimulus) transitions 
that meet our criteria, and then shuffle that list.  Note that for 1 2 3 
we have six such possible transitional pairs, and here is one such list 
for the sake of discussion (note there are 6! = 720 possible such 
shuffled lists for 1 2 3):

1 2
1 3
2 1
2 3
3 1
3 2

Now, I start with the first pair, 1 2, and cross that off the list.  I 
then look for the next unused pair that begins with 2, which in this 
case is 2 1.  So I append the 1 to our full trial sequence (bringing it 
to 1 2 1) and cross that pair off the list.  Then I look for the next 
unused pair that begins with 1 (cycling through to the top of the list 
if necessary), and that brings us to 1 3.  So we append 3 to our full 
sequence.  Next we come to 3 1, and append 1 to our sequence.  Next we 
come to ... oh oh!  No more unused pairs that start with 1 to pick up, 
and we still have 2 3 and 3 2 left over.  Well then, we just move down 
to 3 2 instead, and append 2 to our sequence.  Next we get to 2 3, and 
finally to 3 1, and that brings our full sequence to (drum roll, please),
1 2 1 3 2 3 1.
Please check my work now and make sure that I got it right.  And note 
that our sequence consists of (nStim * (nStim-1) + 1) = 7 trials, and 
starts and ends with 1.  Then try this with some examples of your own 
and see how it works.

Now you merely have to implement that in E-Prime code, and I leave that 
as a programming exercise.  If it were me I might well first work this 
out in Excel with a combination of Excel functions and custom Excel VBA 
macros, starting with the simplest example as above and then scaling up 
to my full stimulus set.  Once I got it all working in Excel I would 
then port it over to E-Prime.

Now here is another way to see the same algorithm, and in a way that may 
make it more programmable.  This time, for each stimulus we make a 
separate list of what stimuli may follow it, and shuffle each list 
separately.  For stimuli 1 2 3 we get three lists, e.g.,

1  2  3
-  -  -
2  1  2
3  3  1

This time, we start by picking one list at random, say, 2.  So we start 
our full trial sequence with 2, and take the next unused item in list 2, 
i.e., 1.  Append that to our sequence (now 2 1), then take the next 
unused item from list 1 to append to our sequence (2 1 2).  Back to list 
2, next unused item is 3, take that (2 1 2 3).  Over to list 3, next 
unused item is 2 (2 1 2 3 2).  Oops!  No more items in list 2.  So 
return that 2 to list 3 and instead take the next item, 1 (2 1 2 3 1). 
Over to list 1, next unused item is 3 (2 1 2 3 1 3).  On to list 3, pick 
up that remaining 1, and we are done:
2 1 2 3 1 3 1.
Voila!  Once again, I now leave this algorithm as an E-Prime programming 
exercise.

Note that this algorithm may be generalized to handle a wide variety of 
randomization with constraint problems.  Finally, astute readers will 
notice that I have here presented a scaled-down version of the beautiful 
algorithm published in Remillard, G., & Clark, J. M. (1999) "Generating 
fixed-length sequences statisfying any given nth-order transition 
probability matrix", Beh Res Meth, Instr, & Computers 31: 235-243  (and 
refined more recently in Remillard, G. (2008) "A program for generating 
randomized simple and context-sensitive sequences", Beh Res Meth 40 (2): 
484-492).  I highly advise all to look at those fine papers.

-- David McFarlane, Professional Faultfinder
"When all is said and told, the 'naturalness' with which we use our 
native tongues boils down to the ease with which we can use them for 
making statements the nonsense of which is not obvious."  Edsger W. 
Dijkstra, "On the foolishness of 'natural language programming'", 
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD667.html .


leylo wrote:
> I'm really new in this world of e-prime, and I am embarassed to post
> this question that will probably make you all laugh, but I would
> really appreciate your help because I'm stuck with this part and I
> have to finish this experiment, and I have to do it fast.
> 
> Problem is:  90 trials of random numbers from 0 to 9, but so that
> every number follow every other once and only once, and consecutive
> presentations are not allowed.
> 
> I guess I would have to use that "No Repeat" Script, but you can get
> the idea from my question that my knowledge of programing is not so
> great, so if someone could explain this to me using my example or if
> someone have some other idea.... that would help me a lot.
> 
> Thanks in advance!

-- 
You received this message because you are subscribed to the Google Groups "E-Prime" group.
To post to this group, send email to e-prime at googlegroups.com.
To unsubscribe from this group, send email to e-prime+unsubscribe at googlegroups.com.
For more options, visit this group at http://groups.google.com/group/e-prime?hl=en.