Random permutation of integers from 1 to n without repetition but for large n

Hi,

I want to use a for loop but iterate through the loop indices in a random order. So I want to have a random permutation of integers 1 to n without repetition. I saw that this can be achieved by simply using the randperm function and something like this would be exactly what I would want:

for i = randperm(n)
    %some code
end

However my problem is that my n might be very large, so that using the randperm function becomes infeasible because generating the whole array of length n would exceed the memory limit. So my question would be if you can achieve the same functionality but without generating the whole array. Instead maybe have a function which only generates one integer at a time or some subpart which is small enough to store while making sure that you never generate the same number twice in a later call to the function.

Alternatively formulated: draw a random number from a pool of integers from 1 to n but each time you draw something remove it from the pool of possible integers you can draw.

Thank you for your help!

[Matt J]

Alternatively formulated: draw a random number from a pool of integers from 1 to n but each time you draw something remove it from the pool of possible integers you can draw.

But you say you don't have enough memory for even 1 copy of the pool. So, how do you propose to keep track of the pool? Alternatively, instead of keeping track of the remaining pool, you could keep a record of numbers already chosen. But that list would grow to size n as the loop approaches completion, which means it must exceed your memory resources at some point.

Your real problem, which is what you should be fousing on is either,

(1) You have not freed up enough previously used memory

(2) Your RAM is unusually small. Buy more.

(3) The n you are considering is unrealistically large and you need to consider an alternative approach to whatever it is you are doing.

[Bruno Luong]

@Matt J The pool can be keep track by bit manipulation, that supposingly 64 times smaller than the randperm(n) memory footprint.

For example 8 Gb RAM can keep track a pool of n=68719476736 (roughly 7e10),whereas randperm(n) of such thing requires 512 Gb.

[Bruno Luong]

@Jonas Peschel what is typically n?

[dpb]

To @Matt J's point besides just enough memory for the one copy of the integer array or the output of whatever is to be done (unless it can be also done one observation at a time), it may well turn out to be that there's not enough time to wait for those N calculations to be completed, anyways...

[Bruno Luong]

@dpb "it may well turn out to be that there's not enough time to wait for those N calculations to be completed, anyways..."

Why? Looping on n=8e9 is totally feasible, whereas storing such permutation vector of this size is not possible for 99% of PC outthere.

[Davide Zorzenon]

See here for a related question

Answer 1

[John D'Errico]

Almost always, when I see someone wanting to solve a problem in this way, it means they are trying to use brute force, thus a brute force exploration of a huge search space, when an optimization tool would be a better choice. And yes, brute force is a reasonable choice for small problems. It is just faster to solve some problems that way than writing better code.

HOWEVER, IF you cannot possibly find a way to solve this problem without the use of brute force, hey its your life, while you sit there waiting for your code to terminate. You can choose how to spend the time. You might get a big book to read while you wait though. Remember, that If your code needs to generate trillions of permutations, you will be there waiting for a long time. Whatever floats your boat. I would be seriously looking to reformulate the problem, were it me.

If you still cannot do so, then one idea might be to use a function that returns the next permutation, given the previous permutation from a vector. That would not be too difficult to write. In fact, it already exists on the FEX, so I would not write it myself anyway. (And the code seems reasonably well written.)

https://www.mathworks.com/matlabcentral/fileexchange/57429-nextperm-v-k

For example:

V = 1:3;
V = nextperm(V)
V =
1     3     2

V = nextperm(V)
V =
2     1     3

V = nextperm(V)
V =
2     3     1

V = nextperm(V)
V =
3     1     2

V = nextperm(V)
V =
3     2     1

V = nextperm(V)
V =
1     2     3

Be carefiul, in that nextperm seems to happily wrap around. So when you have called it factorial(n) times, you need to stop.

[Jonas Peschel]

Hi, thank you all for your help. I am doing a GUI/toolbox to solve a certain class of scheduling problems which grows in complexity very fast approximately with n!, so I am aware that doing brute force/exhaustive search migth be inappropiate at some point for to large n, however its a GUI and the user should decide for him/herself. Also I already have implemented another approach using metaheuristic i.e. genetic algorithm which might be more suitable as you say for large n. The idea behind the question was to make the exact search better by implementing some randomness because at the moment the code iterates through all possible schedules in say lexicographical order which means you are possibly stuck at the same spot on your objective function for a long time, so the idea was to avoid this by searching through the schedules in random order.

So I guess it is not so likely that someone wants to do an exact search on so many schedules that you cant store the randperm(n) because as you say it would take really long time problably and maybe you just would have to draw a small subset of integers from 1 to n! but you dont really know before runtime how long the user intends to run the program and how many schedules you have to search through so I also cant really say what is typical number n. So I was looking for a way to avoid storing the whole 1:n! but instead draw only some subset at a time but avoiding to draw some numbers twice and computing the same schedules again but yeah I dont know how that should work.

Regarding the nextperm function, by chance I already saw that and even tried to use it somewhere else in the code but I dont really get how that would be useful here, so maybe you could explain in more detail please.

Thank you for your help and your effort :)

[Steven Lord]

If n! is that large, why not just call randperm to generate small subsets of the vector 1:n! repeatedly? The odds that you'll generate the same number in multiple subsets is vanishingly small.

n = 1;
while factorial(n) <= 2^53
    n = n + 1;
end
n = n - 1;
fprintf("%d! is %d which is less than %d (2^53).\n", ...
    n, factorial(n), 2^53)

18! is 6402373705728000 which is less than 9007199254740992 (2^53).

I chose 2^53 as the first input to randperm (if it is scalar) must be less than 2^53.

numSubsets = 100;
subsetLength = 1000;
x = zeros(subsetLength, numSubsets);
for k = 1:numSubsets
    x(:, k) = randperm(factorial(n), subsetLength);
end
fprintf("x contains %d unique numbers (%d if all elements are unique).\n", ...
    numel(unique(x(:))), numel(x))

x contains 100000 unique numbers (100000 if all elements are unique).

[John D'Errico]

@Steven Lord

Yes, I agree with your statement. But actually, I have a funny feeling the birthday paradox may take over at some point, that you will start to see repeats. That is, suppose I have a population of 1e12 members? Now, sample randomly from that set with replacement. Multiple samplings with randperm do not insure that no replacement will ever happen. For example, sample 1000 members from the population, using randperm so no replacement is possible in that set. But now, sample a second set of 1000 elements. It will not take many resamplings at all before the probability of a hit against the previous samples grows large. I suppose one trick might be to use a hash table to then quickly exclude the hits.

But is this idea of yours a better way to sample the search space? Very possibly it is, even at the cost of some hits, especially since we can delete the hits as needed. The problem is the nextperm tool will sample a small region of the search space very densely, and one would probably never have time to wander into other regions. A more random sampling does not suffer from that problem.

[Bruno Luong]

@Steven Lord "If n! is that large"

I must miss something; OP just stated that n is large so that randperm(n) (of length n) can not be stored in his PC memory.

This is far worse than n! is large.

[Jonas Peschel]

Hi, thank you for your comments. @Bruno Luong I am sorry my notation was not consistent and a bit confusing. You are right, I just want to have one permutation of one large vector 1:n, for any large n, just by chance in my case n=N!, where N is the number of jobs for the scheduling problem, sorry for my confusing notation.

It feels a bit unsatisfying to rely on pure luck, that nothing is drawn multiple times, I get that the chances are very small maybe but still, if a user was to decide to run through all the possible n's you couldnt even say at one point that everything is computed because you just dont know, if I understood correctly.

I guess maybe I will just not have the randomness but instead just have some stepsize and iterate like that:

i=1:stepsize:n, then i=2:stepsize:n, ... and so on with the correct ending indices and like that avoid to be stuck in one place on the objective function.

Still not really satisfying but yeah I dont know. Thank you all for your help.

[Bruno Luong]

@Jonas Peschel Your verbal desciption is still confuse. How the (wrong) pseudo code

for i = randperm(n)
    %some code
end

should be modified with N?

And I reiterate my earlier question, what typical value of N you aim for?

[Jonas Peschel]

Hi @Bruno Luong the code is correct, n is a large number, in my special case n=N!, where N is some small number, but that is not really relevant for the question. For N>=13, you cant store the whole array: randperm(n) = randperm(factorial(N)) is too large and gives me memory error. N is for me the number of jobs in my scheduling problem so if the user decides to throw in more than 13 jobs I get a problem.

[Bruno Luong]

Is it normal you casecade two permutations and loop on a random permutation of a vector that is the enumerate of all permutations N?

This looks odd to me.

Do you result changes with the for-loop order? If not why not doing something along John's suggestion:

N = 13;
V = 1:N;
n = factorial(N);
for i = 1:n
    % do something with V
    % ...
    V = nextperm(V);
end

In other word I suspect you mix up between randperm(N), perms(1:N) and randperm(n).

[Jonas Peschel]

No, my problem is not generating all the possible schedules/permutations of the vector 1:N, I am already doing something similar to your code. The problem is really to change the order in which the loop goes through these different permutations. Of course if you go through the complete loop the results at the end are the same. But the thing is you might not want to go through the whole loop because it might take really long and so on. Thats why I want to change the order so that you compute very different things/schedules each iteration. So not compute schedules: 12345, 12354, 12435, ... and so on but compute in a totally random order. I hope I made my problem a bit clearer.

[Bruno Luong]

So just do what ImageAnalyst suggests:

N = 13;
n = factorial(N); % or 8e9 whatever large number, n is factorial is really irrelevant
niter = 1e9; % whatever maximum value but <= n you can afford to do
for i = randperm(n,niter) % the size is niter, contains random numbers in 1:n without repetition
    % do something
end

[Jonas Peschel]

Yes, the problem with drawing the same things multiple times remains but yeah I guess thats the best you can do, thank you again.

[Bruno Luong]

@Jonas Peschel "Yes, the problem with drawing the same things multiple times remains"

Certainly not: randperm returns non-replacement drawing, as it supposes to do. so i variable never repeat itself

[Jonas Peschel]

Yes sure, but when you draw the next niter numbers they will be possible duplicates of what you have drawn before.

[Bruno Luong]

And why you "draw" next niter to defeat the purspose of randperm?

That is mainly because your code workflow that is flawed; and beyond the scope of the original question asked above.

Do the whole process in ONE for-loop, as you describe in the original question.

[Jonas Peschel]

I think we talk past each other a bit xD or maybe I am stupid. Of course I want to do it in one loop and only ever draw from randperm ONCE. But I cant do that because n is to large to store the whole array generated by randperm(n). And I want to be able to iterate through more indices than I can store at once.

[Bruno Luong]

"But I cant do that because n is to large to store the whole array generated by randperm(n)."

But we did not tell you to do that, we tell you to generate

iarray = randperm(n,niter);

where niter is reasonably in both of computation time and memory, something about 1e9 for many computers.

It can be generated on mine with niter = 1e9, it take few minutes though with a peak memory above 32 Gb during the array is being geneated, and become 8 Gb + other stuffs when the array is being used.

To keep track of of what has been processes before it would slow down considerably (the complexity become n^2) + whatever you want to do with i. So this is a bad strategy and I doubt you can go up to 1e9 iterations. The randperm function uses perhaps one of the variants of Fisher Yates algoritm and according to this wiki page it is optimum in space and time (both is O(n)). So you won't be able to do it better or make the memory requirement going away, beside use smaller type such as uint32 class.

If that value niter is too small to suit for your need, then do Matt tell you : buy a bigger computer.

[Jonas Peschel]

Ok, thank you all

Answer 2

[Image Analyst]

You ask "looking for a way to avoid storing the whole 1:n! but instead draw only some subset at a time"

Well, randperm allows you to specify some number of elements to be in your subnet. For example for n=5, and n!=120:

n = 5;
subset = randperm(factorial(n), 6) % Retrieve 6 numbers

subset = 1×6

63 62 16 81 50 6

[Bruno Luong]

Why everybody speaks about factorial here? OP wants just to iterate on ONE random permutation where n is large, for example n is world population , ~ 8e9.

[Image Analyst]

@Bruno Luong the original poster said "I just want to have one permutation of one large vector 1:n, for any large n, just by chance in my case n=N!" So I was just going by what he said. To mach his terminology I guess I should have done.

N = 9; % Whatever....
n = factorial(N);
subset = randperm(n, 6) % Retrieve 6 numbers