Optimize repeated permutation of a large vector

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!

[the cyclist]

Just to clarify ...

Suppose instead that s were 2^3 = 8 elements. Suppose that vector is

s = [1 1 0 1 1 0 0 1];

and suppose your cycle lengths are

n1 = 4;
n2 = 3;
n3 = 1;

What is your desired output?

[Shaked Reich]

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.

Answer 1

[Bruno Luong]

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]

If you want "J" as oppose the indexing, prefer sparse format

J = sparse(p, i, 1);
s = s*J % s assumed row-vector

[Shaked Reich]

Thank you Bruno!

the sparse method was exactly what I needed.

This got my Thesis simulation x20 times faster!

much appreciated

[Bruno Luong]

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.

Answer 2

[Bruno Luong]

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