Sampling from very long permutations

1 view (last 30 days)
Giovanni Rosso
Giovanni Rosso on 21 Aug 2015
Commented: Giovanni Rosso on 21 Aug 2015
Hi all, I need to sample permutations from all the possible of N objects. Of course I have a probability vector P for sampling
population = perms(1:N)
y = randsample(1:factorial(N),M,true,P)
sampled = population(y,:)
The problem is that I need to deal with large N (at least 50) and for N>10 the perms(N) command run out of size.
Is there a smarter way to sample from permutations 1:N using P without generating the huge factorial matrix?
Edit: changed the name of all permutations matrix from allperms to population for clarity.

Answers (1)

Walter Roberson
Walter Roberson on 21 Aug 2015
You might be able to do the sampling using less memory, but your probability vector has to match the size of your sample space, so for 50 items your probability vector would have to be 50! elements which is 3.04140932017134e+64 elements. There is no realistic way you would be able to construct a probability vector that big.
If you had a probability formula then we might be able to make progress. But if it is not uniform random probability then the sampling is going to depend upon the arbitrary order that you enumerate the sample space (that is, upon the arbitrary order that you arrange the permutations in.)
Your representative code appears to be taking permutations of permutations -- 1 to factorial(N) would be a permutation index into the permutations of N objects, and you want M of those indices, and then you allperms() those indices??? It would seem more plausible that you would want to sample N objects M at a time and then find all the permutations of the sampled objects, and even more likely that you want to select M random permutations of N objects.
  1 Comment
Giovanni Rosso
Giovanni Rosso on 21 Aug 2015
allperms is not a function but the matrix with all the permutations of N objects. I changed the code so it should be more clear, sorry.
However, I DO have a probability formula and my goal is to select a subset of M permutations of N objects sampling from this probability.

Sign in to comment.

Categories

Find more on Elementary Math in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!