3 views (last 30 days)

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?

David Goodmanson
on 30 May 2020

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]);

David Goodmanson
on 2 Jun 2020

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.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.