On 14/06/07, Will Woods <[EMAIL PROTECTED]> 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 [email protected] http://projects.scipy.org/mailman/listinfo/numpy-discussion
