I have a set of integers, say S = {1,...,10}, and two matrices N and M, whose rows are some (but not necessarily all possible) permutations of elements from S of orders, say, 3 and 5 respectively, e.g. N = [1 2 3; 2 5 3;...], M = [1 2 3 4 5; 2 4 7 8 1;...].
A sub-permutation Q of a permutation P is just an indexed subset of P such that the order of the indices of the elements of Q is the same as the order of their indices in P. Example: [2,4,7] is a sub-permutation of [2,3,4,6,7,1], but [1,2,3] is not a sub-permutation of the latter.
I need an efficient way (e.g. as vectorized as possible and as small for-loops as possible) to find
(1) all permutations from M which have sub-permutations from N
and
(2) how many times each sub-permutation from N is to be found in M.
So far, what I have is a vectorized code that checks if a given single sub-permutation is contained in M (and how many times), but then I have to use a parfor-loop through N, which gets slow for very big N-s. Note that if N is not too big, one could also attack the problem by simply constructing the admissible 5-tuples from the given 3-tuples and compare the result to M, but that can quickly become much slower than simple brute-forcing if N is sufficiently big.
An alternative way to view the problem is as follows: check if N modulo permutations of its rows is a sub-matrix of M in a general sense, i.e. if it is possible to obtain a permutation of the rows of N by deleting elements from M.
Apologies if my question is too elementary, my background is from arithmetic algebraic geometry and representation theory and I am very new to MATLAB.
EDIT: Here is my code for checking presence of a single k-tuple in M: [code]
function [A,f] = my_function(x,M)
%// returns all rows in M that contain x and the absolute frequency of x in M
%// suboptimal for checking combinations rather than permutations byy at least ~ 50%
k = size(x,2);
m = size(M,1);
R = zeros(m,k);
I = R;
Z = I;
for j = 1:k
[R(:,j),I(:,j)] = max((M == x(j)),[],2);
Z(:,j) = R(:,j).*I(:,j);
end
z = zeros(m,k-1);
for j = 1:(k-1)
z(:,j) = (Z(:,j) > 0 & Z(:,j) < Z(:,j+1));
end
[v,~] = find(sum(z,2) == k-1);
A = M(v,:);
f = length(v);
end
Using this function, checking through N is then just a simple matter of a (par)for-loop, which I was hoping to avoid in favor of a faster vectorized solution.
