[Numpy-discussion] randint for long type (permutations)

[Anne Archibald]

On 14/06/07, Will Woods <will.woods at ynic.york.ac.uk> wrote:

> I want to choose a subset of all possible permutations of a sequence of
> length N, with each element of the subset unique. This is then going to
> be scattered across multiple machines using mpi. Since there is a
> one-to-one mapping between the integers in the range 0 <= x < N! and the
> possible permutations, one solution would be to choose M < N! integers
> randomly, check for uniqueness, and then scatter only the integers so
> that individual nodes can construct the permutations. However the
> integers need to be of type long, and randint doesn't work for numbers
> which cannot be converted to int. Any suggestions?

A single integer might not be the best representation of a permutation
(I can't see just now how you encode it, actually). Why not represent
it as a tuple of n integers a_i with a_i<=i? (to get a permutation
from this, treat a_i as an instruction to swap element i with element
a_i). This should be (I haven't proven it but I'm pretty sure) a
bijective representation of permutations. Not very compact, though I
suppose you could use an array of 8-bit integers for n<256. It will
serve as a key in dictionaries, though, and converting from a
permutation in some other representation (as returned by argsort?) to
this shouldn't be too difficult. Converting these to longs is also not
too difficult (sum(a_i[1:]*cumprod(i[1:])) nor is the reverse
operation.

And of course generating the permutation randomly becomes easy.

Also, it's worth noting that if n is even moderately large, n! is such
a staggering number that the probability you will ever generate the
same permutation twice is less than the probability that your data
will be modified undetectably in memory by cosmic rays.

Anne