How to calculate permutation powers

Question

lilly lord 2021-7-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/889882-how-to-calculate-permutation-powers

评论： lilly lord 2021-8-2

采纳的回答： Bruno Luong

在 MATLAB Online 中打开

I have to find higher powers of a permutation. For example if M is a given permutation , then to calculate M^11

M= [ 1 2 3 4 5 6 7 8 9 10; 3 6 8 1 2 4 5 7 10 9]

M^11 the answer should be [1:10;7 1 5 8 4 3 62 10 9];

The code below works well for small permutation but for large permutation and higher power gives error. If any one can help . Thanks in advance

inMat: The input permutation matrix
%       n:      The number of permutations
%      M=[1 2 3 4 5 6; 3 4 1 5 6 2];
Temp=inMat;
Temp1=inMat;
rc=size(Temp);
outMat(1,:)=Temp(1,:);
for j=1:n
for i=1:rc(2)
    r=Temp(:,i);
    outMat(2,i)=Temp1(2,r(2));
end
Temp1=outMat;
end

2 个评论
显示无隐藏无

dpb 2021-8-1

在 MATLAB Online 中打开

 For example if M is a given permutation , then to calculate M^11
M=   [ 1     2     3     4     5     6     7     8     9    10;  3     6     8     1     2     4     5     7    10     9]
M^11 the answer should be [1:10;7 1 5 8 4 3 62 10 9];

I've no klew how you come up with the above as the answer???

Nor what power has to do with it given the sample code that is supposed to work ("for small permutation")...

Can't figure out what it's supposed to do as not everything is defined in the code snippet.

Image Analyst 2021-8-1

在 MATLAB Online 中打开

I agree with dpb (above). No idea how you came up with that answer, or what a "power" of a permutation is. All I know is that M is a matrix, not a permutation.

% M is a matrix, not a permutation of anything that we know of so far.
M = [1 2 3 4 5 6 7 8 9 10; 3 6 8 1 2 4 5 7 10 9]
% With the above M, the bottom row is a permutation of the top row.
% So actually each row is a permutation of the other row.
% Make a new matrix that is a permutation of M:
randomIndexes = randperm(numel(M))
M2 = reshape(M(randomIndexes), size(M))

You can see in the last line I made a permutation of your matrix M using randperm(). But I still have no idea what you mean by the "power" of it. Do you just want to raise it to the 11th power, like

M2 = M2 .^ 11;

????

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Bruno Luong 2021-8-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/889882-how-to-calculate-permutation-powers#answer_758492

在 MATLAB Online 中打开

M=   [ 1     2     3     4     5     6     7     8     9    10;  3     6     8     1     2     4     5     7    10     9]
M = 2×10
     1     2     3     4     5     6     7     8     9    10
     3     6     8     1     2     4     5     7    10     9
S=sparse(M(2,:),M(1,:),1);
[p11,~]=find(S^11);
M11= [M(1,:);p11']
M11 = 2×10
     1     2     3     4     5     6     7     8     9    10
     7     1     5     8     4     3     6     2    10     9

3 个评论
显示 1更早的评论隐藏 1更早的评论

lilly lord 2021-8-2

Thank u very much . Can u plz tell me how to take powers of disjoint cycles using the code u have shared.

lilly lord 2021-8-2

Your answer solved my problem . Thank u . for powers of disjoint cycles i will ask as another question

请先登录，再进行评论。

Answer 2

David Goodmanson 2021-8-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/889882-how-to-calculate-permutation-powers#answer_758732

编辑：David Goodmanson 2021-8-2

在 MATLAB Online 中打开

Hi lilly,

Since the 1:n in the first row is just along for the ride, you don't have to carry it along in the calculation; you can just append it at the end. For the 11th power you have to use n=10 multplciations so it might be less confusing to redifine nnew = n+1 and use nnew-1 multiplications. Anyway, the inner do loop is equivalent to the following iterative mapping process:

n = 10;
inMat = [1:10;
         3 6 8 1 2 4 5 7 10 9]
Temp=inMat;
Temp1=inMat;
rc=size(Temp);
outMat(1,:)=Temp(1,:);
for j=1:n
for i=1:rc(2)
    r=Temp(:,i)
    outMat(2,i)=Temp1(2,r(2));
end
Temp1=outMat;
end
outMat
% alterative 
p0 = inMat(2,:);
p = p0;
for j = 1:n
  p = p0(p);
end
outMat2 = [1:10; p]