Generating all ordered samples with replacement

Hello everybody,

is there a function in Matlab which generates an array containing all ordered samples of length k taken from a set of n elements , that is all the k-tuples where each can be any of the , and whose total number is ?

Or can anybody suggest a simple code to generate all of them? I am guessing it involves the iterative use of datasample function checking that every new generated sample is different from the previous ones, but I couldn't find so far a satisfactory way to write it

Answer 1

[Jan]

A fast C-mex: https://www.mathworks.com/matlabcentral/fileexchange/26242-vchoosekro

If you do not have a C-compiler:

function Y = VChooseKRO_M(X, K)
X  = X(:);
nX = numel(X);
Y  = zeros(nX ^ K, K);
r1 = nX ^ (K - 1);
r2 = 1;
for k = 1:K
    Y(:, k) = repmat(repelem(X, r1, 1), r2, 1);
    r1      = r1 / nX;
    r2      = r2 * nX;
end
end

[Riccardo]

Thanks a lot!

Answer 2

[Guillaume]

For and ,

n = 20;
k = 5;

result = dec2base(0:n^k-1, n);  %generate all n^k samples with replacement, as char vector 0-9 + A-Z
result = result - '0' + 1;      %convert character to numbers 1-10, A-Z get converted to 18+
result(result>17) = result(result>17) - 7  %convert 18+ to 11+

For greater n you'll have to use Jan's answer.

[Riccardo]

Thanks to you too.

Answer 3

[Riccardo]

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

[Guillaume]

No, that's going to be extremely slower than both solutions proposed. You're going to be wasting time generating many permutations that were already generated. Both solutions proposed just enumerate all the combinations, with no guessing.

With your solution, when there's only one row left to generate, the probability that it is returned by datasample will be, extremely small. It's going to take a long time before that last row is generated.

[Riccardo]

Thanks, I have tested with a script for and , and I agree, it's quite slower (around 14 seconds compared with 0.01-0.002 seconds). I just wanted to know if it's formally correct.

[Jan]

Yes, it is formally correct.