Generating all ordered samples with replacement

0
votes

I would like to generate an array which contains all ordered samples of length k taken from a set of n elements {a_1,...,a_n}, that is all the k-tuples (x_1,...,x_k) where each x_j can be any of the a_i (repetition of elements is allowed), and whose total number is n^k.

Is there a built-in function in Matlab to obtain it?

I have tried to write a code that iteratively uses the datasample function, but I couldn't get what desired so far.

3
matlabsampling

3 Answers

2
votes

An alternative way to get all the tuples is based on k-base integer representation.

If you take the k-base representation of all integers from 0 to n^k - 1, it gives you all possible set of k indexes, knowing that these indexes start at 0.

Now, implementing this idea is quite straightforward. You can use dec2base if k is lower than 10:

X = A(dec2base(0:(n^k-1), k)-'0'+1));

For k between 10 and 36, you can still use dec2base but you must take care of letters as there is a gap in ordinal codes between '9' and 'A':

X = A(dec2base(0:(n^k-1), k)-'0'+1));
X(X>=17) = X(X>=17)-7;

Above 36, you must use a custom made code for retrieving the representation of the integer, like this one. But IMO you may not need this as 2^36 is quite huge.

1
votes

What you are looking for is ndgrid: it generates the grid elements in any dimension.

In the case k is fixed at the moment of coding, get all indexes of all elements a this way:

[X_1, ..., X_k] = ndgrid(1:n);

Then build the matrix X from vector A:

X = [A(X_1(:)), ..., A(X_k(:))];

If k is a parameter, my advice would be to look at the code of ndgrid and adapt it in a new function so that the output is a matrix of values instead of storing them in varargout.

1
votes

What about this solution, I don't know if it's as fast as yours, but do you think is correct?

function Y = ordsampwithrep(X,K)
%ordsampwithrep Ordered samples with replacement
%   Generates an array Y containing in its rows all ordered samples with  
%   replacement of length K with elements of vector X
X = X(:);
nX = length(X);
Y = zeros(nX^K,K);
Y(1,:) = datasample(X,K)';
k = 2;
while k < nX^K +1
    temprow = datasample(X,K)';
    %checknew = find (temprow == Y(1:k-1,:));
    if not(ismember(temprow,Y(1:k-1,:),'rows'))
        Y(k,:) = temprow;
        k = k+1;
    end
end
end