# Optimize repeated permutation of a large vector

2 views (last 30 days)
Shaked Reich on 6 May 2021
Commented: Bruno Luong on 8 May 2021
Hi all,
s is a vector of length 2^14, whose elements are -1 or +1.
I need to repeatedly permutate s, in the following way:
the elements are diveded into cycles, that I need to cyclically permutate independently.
the first n_1 elements belongs to the first "cycle", the next n_2 elements belongs to the second, and so forth.
I would love Ideas for how to optimize this process.
* Edit for clarification:
Suppose instead that s were 2^3=8 elements. Suppose that vector is:
s = [1 2 3 4 5 6 7 8];
and suppose the cycle lengths are:
n1 = 4; n2 = 3; n3 = 1;
Then the desired output is:
s = [2 3 4 1 6 7 5 8];
What I have done:
I created a block matrix J consisting of cyclic permutation blocks for each cycle, so I have:
s = J*s;
I use single-precision gpuArray for J and s.
because J is a constant matrix consisting only 0's and 1's, I hope there is a way to speed up this multiplication.
Or perhaps there is another way to solve this?
thanks!
##### 2 CommentsShowHide 1 older comment
Shaked Reich on 7 May 2021
Thank you. In this case, The desired output is:
s = [1 0 1 1 0 0 1 1];
To further clarigy, if s was initialy
s = [1 2 3 4 5 6 7 8];
With the same n1,n2,n3, then the desired output would be:
s = [2 3 4 1 6 7 5 8];
Thank you for your question, I will also add it to the post.

Bruno Luong on 7 May 2021
Edited: Bruno Luong on 7 May 2021
s = [1 2 3 4 5 6 7 8];
i=1:length(s);
n=[4 3 1];
c=cumsum([1 n]);
b=cumsum(ismember(i,c));
p=mod(i+1-c(b),n(b))+c(b)
p = 1×8
2 3 4 1 6 7 5 8
s(p)
ans = 1×8
2 3 4 1 6 7 5 8
Bruno Luong on 8 May 2021
Just wonder why you use J instead of index permutation:
s=rand(1000,100);
p=randperm(size(s,2));
J=sparse(p,1:length(p),1);
tic; t=s*J; toc
Elapsed time is 0.001302 seconds.
tic; t=s(:,p); toc
Elapsed time is 0.000594 seconds.

Bruno Luong on 7 May 2021
Edited: Bruno Luong on 7 May 2021
s = [1 2 3 4 5 6 7 8];
n=[4 3 1];
c=cumsum([0 n]);
p=2:length(s)+1;
p(c(2:end))=c(1:end-1)+1;
s(p)
ans = 1×8
2 3 4 1 6 7 5 8