How to step through vector permutations in a parallel loop, without generating all permutations in advance?
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Shlomo Geva
le 15 Oct 2022
Déplacé(e) : Bruno Luong
le 15 Oct 2022
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 commentaires
David Goodmanson
le 15 Oct 2022
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).
Réponse acceptée
Bruno Luong
le 15 Oct 2022
Modifié(e) : Bruno Luong
le 15 Oct 2022
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
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
1 commentaire
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!