Generating certain permutations

Question

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 n x m, i.e., n rows, m columns.

I have difficulties to come up with a algorithm which enables me to generate a certain amount of permutations (or sequences, how you see fit).

I would be really glad if someone could help me with a algorithm, if possible in Matlab, but a pseudo-algorithm would also be very nice.

I give you 3 examples:

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

(In case you are not familiar with matlab matrix notation, , seperates columns, ; seperates rows.)

V(1) = [1,0,0] 
V(2) = [0,1,0]
V(3) = [0,0,1]

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

The permutations are:

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]

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

The permutations are:

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 matrices W in which each row represents V(i)

For the first case:

W = eye(3)

Herein eye(k) creates an identity matrix of size k x k

For the second case:

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

Herein kron is the kronecker product, and ones(k,l) creates a matrix with ones of size k x l

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

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

Observe two things:

1. When the input N is increased an extra column is added with an extra kronecker product and the identity matrix moves along the vector.
2. When the length of the history M is increased the identity matrices vectors are increased, e.g., eye(4) -> eye(5), ones(4,1) -> ones(5,1).

Answer 1

I guess this satisfies all 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]