Conan

A Barbarian Tool for Constrained Randomization.

Introduction

Psychological experiments sometimes involve presenting subjects with a sequence of simple tasks (trials). To avoid memory effects, the sequence of trials should contain no recognizable patterns, so it must be randomized, often with some systematic conditions to be met. For example, if red and blue visual objects are presented, you may want to avoid more than 4 red objects in sequence or you may want to guarantee equal numbers of red and blue objects within the first and the second half of the experiment.

Synopsis

conan
  A Barbarian Tool for Constrained Randomization
  Version 1.9
  R.Nowagk 1998
usage:
  conan [options]   [ ...]
options:
  -s   on success, write some statistics to 
  -o    on success, write output to  instead of stdout
  -l      sloppy; accept sequences with  bad elements left
  -L         disable the final 'frequency' minimum and 'repeat_min'
             checks (useful with -l)

Note that the randomized output is written to the standard output channel - use -o or the shell to redirect it to a file!

Function

Conan is a generalization of several experiment-specific randomization scripts. It takes a set of n-tuples and a set of constraint definitions as input. A random element of the input set is selected and the given constraints are checked for this element. If no constraint is violated, the selected element is appended to the randomized sequence, otherwise another element is tried. Over time, the input set becomes smaller while the randomized sequence grows. If there is no "good" element left in the input set, the randomized sequence is discarded and a new attempt is started.

echo $? 0

All elements of the input set are appended to the randomized sequence

echo $? 1

Syntax/input error

echo $? 2

No solution can be found

Input

The input set is expected as a plain ASCII table with one column per dimension, one line per element, without comments, table headers etc. All values in one column must have the same number of characters (using one-character codes is the best choice). The dimensions must be sufficient to formulate the desired randomization constraints and to translate the randomized table into a useful trial listing for your experiment.

Constraints

The randomization constraints are listed in a ASCII file, one constraint per line. A constraint is specified as follows:

constraint

[variable] : function [: filter]

Basically, variable is a placeholder for information about the already randomized elements (the potential predecessors of the current element) and about the potential absolute position for the current element. function is one of some predefined ways to specify a restriction/requirement for this aspect of the data.

If variable is omitted, the variable of the previous constraint line is used. This simplifies the specification (and speeds up the calculation) of more then one var>function for the same variable.

If a filter is specified in a constraint, this constraint is checked only if the actual value of variable matches the filter regular expression.

variable

component [component ...]

component

n

column index (1-based), expands to the actual value of column n of the current element

n-m

column and relative element index, expands to the actual value of column n of elements in the randomized sequence (m=1 means the previous one, m=2 the element before etc. etc.)

N

expands to the position of the current element in the randomized sequence (0-based 4-digit number)

N/n

expands to the result of the integer division N/n (0-based 4-digit block number)

N%n

expands to the modulo of the integer division N%n (0-based 4-digit element number within block)

function

repeat_max n

allow maximal n immediate repetitions of the same value

repeat_min n

enforce minimal n immediate repetitions of the same value before switching to a different value; this constraint should not be combined with a filter expression

gap_min n

force minimal n different values between repetitions of the same value

frequency min max

each value must occur minimal min and maximal max times

reject regex

reject current element if value match regex

accept regex

accept current element only if value match regex

filter

A regular expression. If specified for a constraint, this constraint is checked only if the actual variable value matches the filter expression.

The constraints file can also contain the entries

• blocksize m
  
• blockfailures n

Per default, if a sequence cannot be finished, it is discarded completely and the rebuild is started from scratch. If there are block constraints, it can be much more effective to discard only the last block. This is tried "blockfailures" times.

Hints

If you are familiar with a script language, a spread-sheet or a good text processor - use it. It is expensive to translate your problem in the very abstract conan formulation, to provide the correct input and to translate the results back just for a little text sort problem...

The conan script is implemented in awk. It will not win many performance awards. The awk call is hidden in a shell script, but you could try to run it directly in case of problems.

It's easy to formulate constraints which are impossible to fulfill. For complex problems, start with a reduced set of constraints and extend it step by step to find a "quite good" solution first. If you got one, you could still try to find the "ideal" solution by running the randomizer over night

The following script could be used for endless execution until a result is found. But be sure that you don't forget such processes! They could block a workstation for days, weeks, months...

r=2;
while [ $r = 2 ]; do
  conan my.cfg my.set > my.result;
  r=$?;
done

Check your results! It costs only few minutes to count some things in the output table but it may cost days to repeat the experiment...

See the grep manpage for regular expression details.

FAQ

Expand all Collapse all

Is there an alternative?

More ...Less ...
Rando: Primarily applied in experimental psychology, where it is used to create experiment schedules. It even can be applied to other planning-activities that have to met boundary constraints. Rando uses a genetic-algorithm to construct a fulfilled schedule. The program was written as successor of Conan.

The Tool is available in the institute's internal network - just type rando to use it.

• You will find the user documentation here: http://rando.svn.sourceforge.net/viewvc/rando/trunk/doc/user/
• Download: http://downloads.sourceforge.net/rando/Rando1.0Beta-binary.zip?use_mirror=osdn

Back to FAQ start

Are there any examples?

More ...Less ...
You want to present coloured (red, green, blue) objects (circle, square) at different screen positions (left, right, center). This results into 3*2*3=18 possible trials, you choose 8 repetitions which means that your input set has 8*18=144 elements. This could be encoded in the &ltset> file (see also https://cbswiki.cbs.mpg.de/pub/EDV/FuerUser/CoNan/sample.set) as:

r c l
r c r
r c c
r s l
r s r
r s c
g c l
... 137 lines follow

where column 1 encodes the color, column 2 the shape and column 3 the position.

The &ltcfg> file (see also https://cbswiki.cbs.mpg.de/pub/EDV/FuerUser/CoNan/sample.cfg) could now define constraints like:

1     : repeat_max 3
# Maximal 3 objects of the same color (column 1) are allowed in sequence.

2     : repeat_max 4
# Maximal 4 objects of the same shape (column 2) are allowed in sequence.

1 2 3       : gap_min    2
# At least 2 different trials must be present between identical trials.

1-1 1       : frequency  15 16
# All 9 possible color transitions
# (previous trial color -> current trial color)
# must occur 15 or 16 times. Note that "frequency  16 16"
# would fail always since there are only 143 such color
# transitions between the 144 trials

N/48 1      : frequency  16 16
# In each block of 48 trials, each of the 3 colors must occur 16 times.

N/48 3      : frequency  16 16 : 0001
# In the second block of 48 trials, each of the 3 positions
# must occur 16 times.

N%48 1      : reject  0000[br]
# The first trial in each 48-trial block is not allowed to have
# a color of b or r; thus color g is forced for trials 0, 48 and 96.

blocksize      48
blockfailures  20
# Since there are many constraints defined in terms of 48-trial
# blocks, the randomizer is instructed to proceed in
# 48-trial blocks.

Back to FAQ start

What tool can I use to generate permutations?

Varna The Barbarian Tool Varna is a program to generate words of length n with given symbols (permutations). This tool is very helpful to generate the input set for Conan. An extended Barbarian Tool called Red Sonja is coming soon. This tool will combine the permutation generator with a constraint checker to make the generation of constrained randomization much easier. More ...Less ...


Back to FAQ start