[Numpy-discussion] randint for long type (permutations)
Will Woods
w.woods@ynic.york.ac...
Fri Jun 15 08:31:38 CDT 2007
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@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@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
More information about the Numpy-discussion
mailing list