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

Question

Shlomo Geva 2022-10-15

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1826813-how-to-step-through-vector-permutations-in-a-parallel-loop-without-generating-all-permutations-in-a

移动：Bruno Luong 2022-10-15

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?

2 个评论
显示无隐藏无

David Goodmanson 2022-10-15

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 2022-10-15

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 2022-10-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1826813-how-to-step-through-vector-permutations-in-a-parallel-loop-without-generating-all-permutations-in-a#answer_1075628

编辑：Bruno Luong 2022-10-15

在 MATLAB Online 中打开

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