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

[Will Woods]

The range of N I need is from 5-100, which spans the highly likely to 
highly improbable for M around 1000-10000. The permutation can be 
derived from an integer using the algorithm here: 
http://en.wikipedia.org/wiki/Permutation

I have found the solution to the random number generator in the random 
module (I had only looked in numpy.random previously!):

getrandbits(k)
     Returns a python long int with k random bits. This method is 
supplied with the MersenneTwister generator and some other generators 
may also provide it as an optional part of the API. When available, 
getrandbits() enables randrange() to handle arbitrarily large ranges. 
New in version 2.4.

Thanks for all the replies.


Will

Anne Archibald wrote:
> 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
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at scipy.org
> http://projects.scipy.org/mailman/listinfo/numpy-discussion

-- 

Will Woods

York Neuroimaging Centre
The Biocentre
York Science Park
Innovation Way
Heslington
York
YO10 5DG

http://www.ynic.york.ac.uk