Rotating rows until they align with a row above in a matrix

I have a i by n matrix. The matrix contains all the unique permutations of 1:n. I want this code to go through each row and rotate the row and compare it with the rows above to see if it matches any of them, if not, I want it to rotate again, until it has either rotated n times or it finds a match. Right now what I have is

for i = 1:size(D,1)
        if D(i,n+1) == 1
            
        else
            for t = i+1:size(B,1)
                if D(i,1:n) == D(t,1:n)
                    continue
                else
                    D(i,1:n) = circshift(D(i,1:n),1);
                end
            end
        end
end

Where the matrix D is our i by n matrix. The problem is, this only rotates a row one time if it does not find a match, and then it moves on to the next row. I am not sure if I need to use a while loop or something? I will take any advise you have.

Thank you.

Answer 1

[Dave B]

It sounds like you want to apply circshift to each row of a matrix, for all of the possible shifts (the width of the matrix), and each time compare it to the rows above to see if it's an exact match.

Here's a test matrix, it always makes it easier to solve these kinds of problems with some simple data (and it makes it easier to explain your question/expectation)

M=[1 2 3 4; 
    2 3 4 1;  % shift by 1
    3 4 1 2;  % shift by 2
    6 5 4 3;  % no matches
    4 1 2 3;  % shift by 3
    1 1 1 1;  % no matches
    5 4 3 6]; % shift by 1

Here's a long version of a solution. Notice that I broke it out into a lot of steps - as you write the code it is really helpful to look at each step and see if you get what you expected. You can debug or use disp to see if each step goes as expected.

for i = 2:size(M,1) % for each row of M
    thisrow=M(i,:);
    % need to check against all previous rows
    for shift = 1:size(M,2)-1 % for all possible shifts
        % shift the row:
        thisshiftedrow=circshift(thisrow,shift);
        % compare to all rows above
        compare=thisshiftedrow==M(1:i,:); % note that that is a i x size(M,2) matrix
        match=all(compare,2); % this is true if it matches a row
        if any(match)
            M(i,:)=thisshiftedrow;
            continue;
        end
    end
end

Notes: I started with the second row, there's nothing above the first one to compare. I also only try width-1 shifts, shifting by width is the original data. Also notice the use of any and all - one confusing thing about your code is that you used == to compare two vectors...that will return a vector, is that what you expect? Using == to compare a row with a matrix is a neat trick to do a bunch at once, the all(...,2) returns true if a whole row is a match. Alternatively, you could use isequal to check for an 'exact' match between one row and another.

Here's a more concise version (just removing the separate variable assignments):

for i = 2:size(M,1)
    for shift = 1:size(M,2)-1
        c=circshift(M(i,:),shift);
        if any(all(c==M(1:i,:),2))
            M(i,:)=c;
            continue
        end
    end
end

Note that there are probably more efficient solutions here if your data are really big (consider - do you need to compare to all previous rows? Any that have already matched one above them are redundant comparisons).

[Spencer Giglio]

This works great, thank you for the help and all the explanation.