Re: Question on partitioning a set of agents.

[Theodore C. Belding]

It may be unbiased (assuming you set the probability to be 1/(current list
size) instead of 1/N), but it's horribly inefficient for large lists,
since it's O(n^2) --- it requires N passes through the list. Some time
ago, I wrote a Shuffler object that shuffled a list of objects in one
pass, using Knuth's [1] algorithm. It should still be on the Swarm web
pages or ftp site somewhere. Once you've shuffled (randomly permuted) the
list, you can take the first N/M objects, stick them in the first
partition, etc. (where M is the number of partitions). If you don't want
to shuffle the list of objects itself, shuffle a list of integers 
1, ..., N and use those as indices.
-Ted

[1] Knuth, D. E. (1998). The Art of Computer Programming. Vol. 2:
Seminumerical Algorithms. 3rd ed. Addison-Wesley. p. 145.

--
Ted Belding                              address@hidden 
University of Michigan Center for the Study of Complex Systems
Homepage: http://www-personal.umich.edu/~streak/
PGP key:  http://www-personal.umich.edu/~streak/pgp-key.html

On Fri, 6 Aug 1999, Jason Alexander wrote:

> For one of my models I need to randomly partition a set of agents
> (stored as a list) into N disjoint classes, where each class is
> equiprobable.
> 
> Are there any implicit biases in the following procedure that I'm
> unaware of?  (It seems okay to me.)
> 
> Let L denote the list of agents.
> Assume RandomFloat() return a number between 0 and 1.
> 
> for i=1 upto N-1 {
>   loop over L {
>      if RandomFloat < 1/N {
>         remove current agent from L
>         insert current agent into class i
>      }
>   }
> }
> Copy remaining agents from L into class N.
> 
> 
> Cheers,
> 
> Jason
> 
> 
>                   ==================================
>    Swarm-Modelling is for discussion of Simulation and Modelling techniques
>    esp. using Swarm.  For list administration needs (esp. [un]subscribing),
>    please send a message to <address@hidden> with "help" in the
>    body of the message.
>                   ==================================
> 



                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================