Eliminating and counting rows that contain a pattern that already appeared
1 Ansicht (letzte 30 Tage)
Ältere Kommentare anzeigen
Spencer Giglio
am 28 Mai 2020
Kommentiert: David Goodmanson
am 2 Jun. 2020
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?
0 Kommentare
Akzeptierte Antwort
David Goodmanson
am 30 Mai 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]);
2 Kommentare
David Goodmanson
am 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.
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Matrix Indexing finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!