Clever Geek Handbook

Making some permutations

I have 2 variables ... the number of inputs N and the length of the history M. These two variables determine the size of the matrix V, which is nxm, i.e. n rows, m columns.

I am having a hard time finding an algorithm that allows me to generate a certain number of permutations (or sequences, as you see fit).

I would be very glad if someone could help me with the algorithm if possible in Matlab, but the pseudo-algorithm will be very nice too.

I will give you 3 examples:

  • If the number of inputs is N = 1 and the history length is M = 2, I have (M + 1) ^ N different combinations, in this case 3. Permutations:

(If you are not familiar with Matlab matrix notation, ,

split columns, ;

split rows.)

V(1) = [1,0,0] 
V(2) = [0,1,0]
V(3) = [0,0,1]
  1. If the number of inputs is N = 2 and the history length is M = 2, I have (M + 1) ^ N different combinations, in this case 9.

Permutations:

V(1) = [1,0,0; 1,0,0]
V(2) = [1,0,0; 0,1,0]
V(3) = [1,0,0; 0,0,1]
V(4) = [0,1,0; 1,0,0]
V(5) = [0,1,0; 0,1,0]
V(6) = [0,1,0; 0,0,1]
V(7) = [0,0,1; 1,0,0]
V(8) = [0,0,1; 0,1,0]
V(9) = [0,0,1; 0,0,1]
  1. If the number of inputs is N = 3 and the history length is M = 3, I have (M + 1) ^ N different combinations, in this case 64.

Permutations:

V(1)  = [1,0,0,0; 1,0,0,0; 1,0,0,0] 
V(2)  = [1,0,0,0; 1,0,0,0; 0,1,0,0]
V(3)  = [1,0,0,0; 1,0,0,0; 0,0,1,0]
V(4)  = [1,0,0,0; 1,0,0,0; 0,0,0,1]
V(5)  = [1,0,0,0; 0,1,0,0; 1,0,0,0]
        ...
V(8)  = [1,0,0,0; 0,1,0,0; 0,0,0,1]
V(9)  = [1,0,0,0; 0,0,1,0; 1,0,0,0]
        ...
V(16) = [1,0,0,0; 0,0,0,1; 0,0,0,1]
V(17) = [0,1,0,0; 1,0,0,0; 1,0,0,0]
        ...
V(64) = [0,0,0,1; 0,0,0,1; 0,0,0,1]

Edit: I just found a way to generate really large W matrices in which each row represents V (i)

In the first case:

W = eye(3)

Here eye(k)

, a kxk identity matrix is ​​created

For the second case:

W = [kron(eye(3),    ones(3,1)), ...
     kron(ones(3,1),    eye(3))]

Here kron

is the kronecker product , and ones(k,l)

creates a matrix with dimensions of size kxl

In the third case:

W = [kron(kron(eye(4),    ones(4,1)), ones(4,1)), ...
     kron(kron(ones(4,1),    eye(4)), ones(4,1)), ...
     kron(kron(ones(4,1), ones(4,1)),    eye(4))]

We have now created matrices W in which each row represents V (i) in vector form, V (i) is not yet a matrix.

Observe two things:

  • As the input N increases, an additional column is added with an additional kronecker product, and the identity matrix moves along the vector.
  • As the history length M increases, the vectors of identical matrices increase, for example, eye (4) → eye (5), units (4,1) → units (5,1).
+3


source to share


3 answers


I assume this suits all of your requirements. Even the order seems correct to me:

M=3;N=3;
mat1=eye(M+1);
vectors=mat2cell(repmat(1:M+1,N,1),ones(N,1),[M+1]);

Super efficient Cartesian product taken from here :



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n = numel(vectors); %// number of vectors
combs = cell(1,n); %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order
combs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n); %// reshape to obtain desired matrix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    

V=cell(size(combs,1),1);
for i=1:size(combs,1)
    for j=1:size(combs,2)
        V{i,1}=[V{i,1};mat1(combs(i,j),:)];
    end
end

Outputs:

M=2,N=2;

V=

[1,0,0;1,0,0]
[1,0,0;0,1,0]
[1,0,0;0,0,1]
[0,1,0;1,0,0]
[0,1,0;0,1,0]
[0,1,0;0,0,1]
[0,0,1;1,0,0]
[0,0,1;0,1,0]
[0,0,1;0,0,1]

M=3;N=3;  %order verified for the indices given in the question

V(1)  = [1,0,0,0; 1,0,0,0; 1,0,0,0] 
V(2)  = [1,0,0,0; 1,0,0,0; 0,1,0,0]
V(3)  = [1,0,0,0; 1,0,0,0; 0,0,1,0]
V(4)  = [1,0,0,0; 1,0,0,0; 0,0,0,1]
V(5)  = [1,0,0,0; 0,1,0,0; 1,0,0,0]
        ...
V(8)  = [1,0,0,0; 0,1,0,0; 0,0,0,1]
V(9)  = [1,0,0,0; 0,0,1,0; 1,0,0,0]
        ...
V(16) = [1,0,0,0; 0,0,0,1; 0,0,0,1]
V(17) = [0,1,0,0; 1,0,0,0; 1,0,0,0]
        ...
V(64) = [0,0,0,1; 0,0,0,1; 0,0,0,1]
+3


source


You can generate them by looking at the M + 1 base entry.

Each digit in this base determines how much of your matrix should be set to 1 on each row.

function V=makeperm(i,N,M)
i = i - 1;
V = zeros(N,M+1);
P = M+1;
% Generate digits in base P
for row = N:-1:1
    col=mod(i,P)+1;
    i=floor(i/P);
    V(row,col)=1;
end


This function will perform the i-th permutation for inputs N, M.

eg.

makeperm(17,3,3)
ans =

0   1   0   0
1   0   0   0
1   0   0   0
+2


source


This code uses allcomb tool from MATLAB file-exchange

to generate decimal numbers corresponding to each line V

. The code allcomb

can be obtained from here .

The working code for solving the mentioned problem would be -

power_vals = power(2,M:-1:0);
pattern1 = repmat({power_vals},1,N);
dec_nums = allcomb(pattern1{:});

bin_nums = fliplr(de2bi(num2str(dec_nums,'%1d').'-'0')); %//'
Vout = permute(reshape(bin_nums,N,size(bin_nums,1)/N,[]),[1 3 2]);

So the nth

3D slice Vout

will represent V(n)

.

Example run -

C M = 2

and N = 2

you will have -

>> Vout
Vout(:,:,1) =
     1     0     0
     1     0     0
Vout(:,:,2) =
     1     0     0
     0     1     0
Vout(:,:,3) =
     1     0     0
     0     0     1
Vout(:,:,4) =
     0     1     0
     1     0     0
Vout(:,:,5) =
     0     1     0
     0     1     0
Vout(:,:,6) =
     0     1     0
     0     0     1
Vout(:,:,7) =
     0     0     1
     1     0     0
Vout(:,:,8) =
     0     0     1
     0     1     0
Vout(:,:,9) =
     0     0     1
     0     0     1
+2


source






More articles:


All Articles