Creating separate combinations with repetition

74 views (last 30 days)
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

Answers (1)

Bruno Luong
Bruno Luong on 25 Apr 2021
Edited: Bruno Luong on 26 Apr 2021
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)

Products


Release

R2021a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!