Eliminating and counting rows that contain a pattern that already appeared

Below is my code. What is does is generates all the possible permutations for a number n, Then it finds all the permutation differences for all of the rows and then takes what would be a n! by n matrix and makes it a n! by 2*n matrix and places the columns 1:n into the columns n+1:2*n. What I want to find is all of the rows that contain the same n length pattern somewhere in the columns. See Below:

function [sigma,A,B] = SigPerm(n)
    %create matrix A, the set of all permutations 
    v = 1:n;
    A = perms(v);
    
    %Create matrix B, the set of all permutation differences with one cycle
    %added
    B = zeros(factorial(n),2*n);
    for i = 1:factorial(n)
        for t = 1:n-1
            B(i,t) = mod(A(i,t+1)-A(i,t),n);
        B(i,n) = mod(A(i,1)-A(i,n),n);
        end
        B(i,n+1:2*n) = B(i,1:n);
    end
end

for lets say n = 5, We get a 120x10 matrix. Looking at the first 10 rows:

What I want is to group all the rows that contain unique patterns together. For example, row 1 would be alone, row 2 which has a pattern of [4 4 3 1 3] would group with rows 3, 7, and 10 as all of those rows contain the pattern [4 4 3 1 3] somewhere in their columns. Rows 4 and 5 would group together with the pattern [4 3 4 2 2] and rows 6, 8, and 9 would not group with any of the first 10 rows.

Is there a way I can count how rows contain the pattern and eliminate any rows that repete a pattern that is already present?

Answer 1

[David Goodmanson]

Hello Spencer,

I assume that the patterns you mean have a length of 5. The way that you have set the the problem, 44313 (B row 2) is a pattern, but looking just at the first five columns of B, then 344431 (B row 10), which is a cyclic (circular) permutation of 44313 is the same pattern. That's because in B row 10, the sixth column is a 3, so 44313 appears. For the first five columns of B, all five of these cyclic permutations are really the same pattern:

% example of rows of B, first five columns
44313
34431
13443
31344
43134

If you go back to all 120 permutations and then apply the mod process to obtain B, you will find that there are only eight possible patterns:

% patterns, first five rows of B
1 1 1 1 1  
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4

1 1 2 4 2     + cyclic permutations
2 2 4 3 4     + cyclic permutations
3 3 1 2 1     + cyclic permutations
4 4 3 1 3     + cyclic permutations

The patterns divide the permutations into eight groups (equivalence classes). The first four patterns have 5 permutations each, and the last four patterns (including cyclic permutations) have 25 permutations each.

It's going to be convenient to have a unique integer index for each pattern, and one approach (somewhat arbitrary but it works) is the sum of squares of the components of B. For each pattern Bpattern with five elements,

m = sum(Bpattern.^2) gives for the eight patterns above

    5
    20
    45
    80
    
    26
    49
    24
    51   

Note that m is not affected by a cyclic permutation of the pattern. The following code sets out perms(1:5) preceded by a row index and followed by index m and the pattern. Any two rows with the same m share the same pattern, counting cyclic permutations as the same.

n = 5;
A = perms(1:n);
Bnew = mod(circshift(A,-1,2)-A,n);    % same as what you did
m = sum(Bnew.^2,2);

disp([blanks(4) 'row' blanks(4) '-------permutation-------'...
        blanks(5) 'm' blanks(5) '------------B------------'])
disp(' ')
disp([(1:factorial(n))' A m Bnew]);

[Spencer Giglio]

This works perfectly for n = 5 or less but I am seeing that it does not work for 7 or 9. Do you have any ideas on how to apply it to greater sets as below for 9 as an example?

-m- ------------------------Bnew-----------------------

576 8 8 8 8 8 8 8 8 8

483 8 8 8 8 8 8 7 1 7

483 8 8 8 8 8 7 1 7 8

473 8 8 8 8 8 7 8 2 6

473 8 8 8 8 8 6 2 8 7

394 8 8 8 8 8 6 1 1 6

483 8 8 8 8 7 1 7 8 8

392 8 8 8 8 7 1 6 1 7

473 8 8 8 8 7 8 2 6 8

467 8 8 8 8 7 8 8 3 5

461 8 8 8 8 7 7 3 7 7

384 8 8 8 8 7 7 1 2 5

473 8 8 8 8 6 2 8 7 8

because here we would have that (using your syntax from above)

m = sum(Bnew.^2,2);

where m for rows 2 and 3 are equal at 473, but they have different cyclic permutations

I think the biggest issue is that for these higher values of n it is possible to have the same integers in a different, noncyclic permutation for example 1 2 3 4 5 6 7 8 9 and 1 2 3 5 4 6 7 8 9, so I would not want to count these as the same but I would want to count 1 2 3 4 5 6 7 8 9 the same as 2 3 4 5 6 7 8 9 1.

Any thoughts?

[David Goodmanson]

Assuming a cyclic permutations to be equvialent, in the original list of permutations you can permute 1 to the first position, so the initial list, rather that being perms(n), is

A = [ones(fac(n-1),1) perms(2:n)]

so that at least reduces things by a factor of n. But when you create B from that set, it looks like you can still have [1] cyclic permutations of the resulting patterns, which are equivalent, and [2] inequivalent patterns with the same collection of digits like in the 473 case above. It does not appear to be that easy to do a sort where case [1] instances are put together and case [2] instances are kept apart.