How to step through vector permutations in a parallel loop, without generating all permutations in advance?

I need a paralleised loop to step through all permutations of 1:N

Even though for some values of N it is computationally feasible, N may be too large to precompute all permutations and then step through in a simple parfor loop. It takes up too much memory. A simple solution for one worker is to just use something like p = nextperm(p), to get the next permutation in, say, lexigoraphic order. But to execute it in parallel I need a mutually exclusive resource, something like p = mutexNextPerm(), which returns the next permutation not yet processed by any worker. Only a single copy of the function must exist to serve all workers; the function mutexNextPerm() can then call p = nextperm(p) and keep track of the last p served.

Can this be done in MATLAB?

[David Goodmanson]

Hi Shlomo,

I take it that the nextperm function is considered to be a given. Perhaps in mutexnextperm you could declare the most recent permutation p to be a persistent variable, and then each time that mutexnextperm is called, output nextperm(p) and update p with nextperm(p).

[Shlomo Geva]

Thanks David,

The issue with parfor is that there will be private copies of mutexNextperm() - one in each worker thread; unless I misunderstand how it works. Persistent variables won't work. Each copy will have its own persistent variable p.

parfor supports only a limited set of reductions (like max, min, union, intersect, and some other).

I am essentially looking for a jail break... Maybe SPMD or something else?

Answer 1

[Bruno Luong]

function getenumperm bellow enumerates the permutation of 1:n

n = 4;
for k=1:factorial(n) % or parfor
    p = getenumperm(k, n)
    ... do something with p
end

p = 1×4

1 2 3 4

p = 1×4

1 2 4 3

p = 1×4

1 3 2 4

p = 1×4

1 4 2 3

p = 1×4

1 3 4 2

p = 1×4

1 4 3 2

p = 1×4

2 1 3 4

p = 1×4

2 1 4 3

p = 1×4

3 1 2 4

p = 1×4

4 1 2 3

p = 1×4

3 1 4 2

p = 1×4

4 1 3 2

p = 1×4

2 3 1 4

p = 1×4

2 4 1 3

p = 1×4

3 2 1 4

p = 1×4

4 2 1 3

p = 1×4

3 4 1 2

p = 1×4

4 3 1 2

p = 1×4

2 3 4 1

p = 1×4

2 4 3 1

p = 1×4

3 2 4 1

p = 1×4

4 2 3 1

p = 1×4

3 4 2 1

p = 1×4

4 3 2 1

function p = getenumperm(k, n)
% Get a permutation from enumerate number k
p = zeros(1,n);
i = 1:n;
f = factorial(n-1);
for j=n:-1:1
    r = ceil(k/f);
    k = mod(k-1, f)+1;
    p(i(r)) = n-j+1;
    i = i([1:r-1 r+1:n r]);
    f = f/(j-1);
end
end

[Shlomo Geva]

Thanks. That works for me.