Sampling from very long permutations
2 次查看(过去 30 天)
显示 更早的评论
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.
0 个评论
回答(1 个)
Walter Roberson
2015-8-21
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.
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!