[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Question on partitioning a set of agents.
From: |
Theodore C. Belding |
Subject: |
Re: Question on partitioning a set of agents. |
Date: |
Sun, 8 Aug 1999 03:55:38 -0400 (EDT) |
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.
==================================