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

This code uses allcomb tool from MATLAB file-exchange to generate the decimal numbers corresponding to each row of V. The code for allcomb can be obtained from here.

The working code to solve the stated 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]);

Thus, the nth 3D slice of Vout would represent V(n).

Sample run -

With M = 2 and N = 2, you would 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

Answer 2

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]

Answer 3

You can generate these by considering the input in base M+1.

Each digit in this base specifies which part of your matrix should be set to 1 in 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 produce the i^th permutation for inputs of N,M.

e.g.

makeperm(17,3,3)
ans =

0   1   0   0
1   0   0   0
1   0   0   0