Creating separate combinations with repetition

Hello all!

I'm trying to create a combination with repetitions but in smaller poriions. The idea is that I want to work with a large table of all possible combinations but due to its space consumption, I thought of generating that same table but split in parts. I would work on the first part (i.e. the first 1000 rows), then delete, and work on the next 1000 rows of the table.

This is an example of a combination w/ repetitions:

B =

     1     1
     1     2
     2     2

I need this result as shown below without first generating the whole combination.

B1 =

     1     1
     
B2 =

     1     2
     
B3 =

     2     2
     

Of course, the table are much larger than this but I'm not sure how to approach this. After some search, I found a nice code that generates B as shown on the top but I'm not very sure how to break it down without generating the big table first.

A = [1 2];

B = nmultichoosek(A,2)

function combs = nmultichoosek(values, k)
%// Return number of multisubsets or actual multisubsets.
if numel(values)==1
    n = values;
    combs = nchoosek(n+k-1,k);
else
    n = numel(values);
    combs = bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);
    combs = reshape(values(combs),[],k);
end
end

Let me know if the question doesn't make sense.

Thanks!

Yeray

[Walter Roberson]

https://www.mathworks.com/matlabcentral/answers/623358-get-a-combination-of-unique-paths-for-given-pair-of-numbers#comment_1082638

Answer 1

[Bruno Luong]

I program a function nchoosek_enum that is almost like nchoosek, excepted that you can pass an enumerated array i that selects the combination.

Note that if i value is outside 1:nchoosek(n,k), it will return a combination vector containing NaN.

Typically you can the function in this manner to process by chunk (here is 10 combinations at the time)

n = 10;
k = 3;

chunksize = 10;
i = 1:chunksize;
norepetition = false;
while true
    if norepetition
        c = nchoosek_enum(n, k, i);
    else
        c = nchoosek_enum(n+k-1, k, i);
        c = c - (0:k-1);
    end
    for r=1:size(c,1)
        cr = c(r,:);
        endcomb = any(isnan(cr));
        if endcomb
            break
        end
        % do somthing with cr
        fprintf('%s\n', mat2str(cr))
    end
    if endcomb
        break
    end
    i = i + chunksize;
end

[1 1 1]
[1 1 2]
[1 1 3]
[1 1 4]
[1 1 5]
[1 1 6]
[1 1 7]
[1 1 8]
[1 1 9]
[1 1 10]
[1 2 2]
[1 2 3]
[1 2 4]
[1 2 5]
[1 2 6]
[1 2 7]
[1 2 8]
[1 2 9]
[1 2 10]
[1 3 3]
[1 3 4]
[1 3 5]
[1 3 6]
[1 3 7]
[1 3 8]
[1 3 9]
[1 3 10]
[1 4 4]
[1 4 5]
[1 4 6]
[1 4 7]
[1 4 8]
[1 4 9]
[1 4 10]
[1 5 5]
[1 5 6]
[1 5 7]
[1 5 8]
[1 5 9]
[1 5 10]
[1 6 6]
[1 6 7]
[1 6 8]
[1 6 9]
[1 6 10]
[1 7 7]
[1 7 8]
[1 7 9]
[1 7 10]
[1 8 8]
[1 8 9]
[1 8 10]
[1 9 9]
[1 9 10]
[1 10 10]
[2 2 2]
[2 2 3]
[2 2 4]
[2 2 5]
[2 2 6]
[2 2 7]
[2 2 8]
[2 2 9]
[2 2 10]
[2 3 3]
[2 3 4]
[2 3 5]
[2 3 6]
[2 3 7]
[2 3 8]
[2 3 9]
[2 3 10]
[2 4 4]
[2 4 5]
[2 4 6]
[2 4 7]
[2 4 8]
[2 4 9]
[2 4 10]
[2 5 5]
[2 5 6]
[2 5 7]
[2 5 8]
[2 5 9]
[2 5 10]
[2 6 6]
[2 6 7]
[2 6 8]
[2 6 9]
[2 6 10]
[2 7 7]
[2 7 8]
[2 7 9]
[2 7 10]
[2 8 8]
[2 8 9]
[2 8 10]
[2 9 9]
[2 9 10]
[2 10 10]
[3 3 3]
[3 3 4]
[3 3 5]
[3 3 6]
[3 3 7]
[3 3 8]
[3 3 9]
[3 3 10]
[3 4 4]
[3 4 5]
[3 4 6]
[3 4 7]
[3 4 8]
[3 4 9]
[3 4 10]
[3 5 5]
[3 5 6]
[3 5 7]
[3 5 8]
[3 5 9]
[3 5 10]
[3 6 6]
[3 6 7]
[3 6 8]
[3 6 9]
[3 6 10]
[3 7 7]
[3 7 8]
[3 7 9]
[3 7 10]
[3 8 8]
[3 8 9]
[3 8 10]
[3 9 9]
[3 9 10]
[3 10 10]
[4 4 4]
[4 4 5]
[4 4 6]
[4 4 7]
[4 4 8]
[4 4 9]
[4 4 10]
[4 5 5]
[4 5 6]
[4 5 7]
[4 5 8]
[4 5 9]
[4 5 10]
[4 6 6]
[4 6 7]
[4 6 8]
[4 6 9]
[4 6 10]
[4 7 7]
[4 7 8]
[4 7 9]
[4 7 10]
[4 8 8]
[4 8 9]
[4 8 10]
[4 9 9]
[4 9 10]
[4 10 10]
[5 5 5]
[5 5 6]
[5 5 7]
[5 5 8]
[5 5 9]
[5 5 10]
[5 6 6]
[5 6 7]
[5 6 8]
[5 6 9]
[5 6 10]
[5 7 7]
[5 7 8]
[5 7 9]
[5 7 10]
[5 8 8]
[5 8 9]
[5 8 10]
[5 9 9]
[5 9 10]
[5 10 10]
[6 6 6]
[6 6 7]
[6 6 8]
[6 6 9]
[6 6 10]
[6 7 7]
[6 7 8]
[6 7 9]
[6 7 10]
[6 8 8]
[6 8 9]
[6 8 10]
[6 9 9]
[6 9 10]
[6 10 10]
[7 7 7]
[7 7 8]
[7 7 9]
[7 7 10]
[7 8 8]
[7 8 9]
[7 8 10]
[7 9 9]
[7 9 10]
[7 10 10]
[8 8 8]
[8 8 9]
[8 8 10]
[8 9 9]
[8 9 10]
[8 10 10]
[9 9 9]
[9 9 10]
[9 10 10]
[10 10 10]

function c = nchoosek_enum(n, k, i)
% c = nchoosek_enum(n, k, i)
% n: nonnegative integer scalar
% k: nonnegative integer scalar <= n
% i vector of integers, values in (1:nchoosek(n,k))
%
% returns a (m x k) matrix containing combinations of the elements of
% vector (1:n) taken k at a time and enumerated by i. m is length(i).
%
% See also; nchoosek

if ~isscalar(n)
    v = n;
    n = length(v);
else
    v = 1:n;
end
if nargin < 3
    c = nchoosek(1:n,k);
else
    P = PascalTriangle(n-1);
    i = reshape(i, 1, []);
    c = nchoosek_helper(n, k, i, 0, P);
end
if ~isequal(v,1:n)
    b = ~isnan(c);
    c(b) = v(c(b));
    c = feval(class(v),c);
end
end

%% Recursive engine
function c = nchoosek_helper(n, k, i, o, P)
if k == 0
    c = zeros(numel(i),0);
else
    nq = P(n:-1:k+1,k);
    p = cumsum([0; nq]);
    [~,j] = histc(i-1, p); %#ok
    c = nan(numel(i),k);
    k = k-1;
    for q = unique(j(j>0))
        b = j == q;
        c1 = o+q;
        cj = nchoosek_helper(n-q, k, i(b) - p(q), c1, P);
        c(b,:) = [repmat(c1, size(cj,1), 1), cj];
    end
end
end

%% Compute Pascal triangle
function P = PascalTriangle(n)
if n==0
    P = 1;
else
    P = PascalTriangle(n-1);
    p = P(n,:);
    P = [P, zeros(n,1);
         1, p(1:n-1)+p(2:n), 1];
end
end

EDIT: bug corrected due to discretize that treats last bin differently (deserved "frustration" feature)