[Gridflowdev] feature request: [#shuffle]
Mathieu Bouchard
matju at artengine.ca
Wed Jan 11 14:26:18 EST 2006
On Wed, 11 Jan 2006, Claude HeilandAllen wrote:
> I'm working on something, and would find it really handy to have a
> [#shuffle] object that would take an input grid's 'vectors' and swap
> them with each other to give a random permutation.
If you have N independent uniform variates on a large enough interval of
integers, then their joint distribution will be symmetric in a way that no
matter how you permute the variates you still get the same distribution
(the symmetry group has N! elements). Then look at possible orderings as
being a permutation variate, dependent on all N uniform variates. It
inherits that symmetry and therefore all N! possibilities are equally
likely.
Therefore,
[42 # 1000000000}

[#grade] generates a uniformly random permutation of numbers 0..N1

[#outer ignore (0)] add dimension to please #store

[#store (42 # ...)]

random permutation of 42 values
> inlet 0 method grid (grid(d0 d1 d2 ... dN) grid)
the convention is that the last dimension is labeled d(N1) so that the
number of dimensions is N instead of N+1.
The running time is O(n log n) because that's how [#grade] is. If you want
something in O(n) it's gotta be in C++ or be rather slow, unless there's a
trick I haven't thought of.
> for(int i_(D1) = 0; i_(D1) < dim_(D1) {
> Swap(grid[ i_0 ][ i_1 ]...[ i_(D1) ],
> grid[Rand(dim_0)][Rand(dim_1)]...[Rand(dim_(D1))])
> }
> Is there a faster algorithm out there to randomly permute?
> (I admit I haven't looked...)
It can't get any faster than that.
> What are the chances of this being implemented and debugged by anyone
> other than myself within two weeks?
do you need it to be faster than the one using [#grade] above?
_ _ __ ___ _____ ________ _____________ _____________________ ...
 Mathieu Bouchard  tél:+1.514.383.3801  http://artengine.ca/matju
 Freelance Digital Arts Engineer, Montréal QC Canada
More information about the Gridflowdev
mailing list