[Gridflow-dev] feature request: [#shuffle]

[Mathieu Bouchard]

On Wed, 11 Jan 2006, Claude Heiland-Allen 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..N-1
 |
[#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(N-1) 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_(D-1) = 0; i_(D-1) < dim_(D-1) {
>        Swap(grid[       i_0 ][       i_1 ]...[       i_(D-1) ],
>             grid[Rand(dim_0)][Rand(dim_1)]...[Rand(dim_(D-1))])
>      }
> 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