MATLAB Answers

k distinct combinations of size p without replacement

70 views (last 30 days)
Eric Schols
Eric Schols on 13 Jan 2016
Edited: Shlomo Geva on 4 Dec 2020
I have the number 1,2,...,N and from them I want to take k distinct combinations of size p without repetition.
For example, if N = 10, k = 4 and p = 3, a possible desired outcome would be:
1 4 9
9 4 2
3 5 2
1 8 4
But not:
1 4 9
9 4 2
3 5 2
1 9 4
since [1 4 9] and [1 9 4] are the same combination. Nor do I want output like [1 1 4], since the number 1 occurs twice, and I want without repetition.
I've looked into a lot of Matlab functions (some of them on the file exchange), like COMBINATOR, PERMS, RANDPERM, NCHOOSEK, KTHCOMBN, but none do exactly what I'm asking, and I don't know how to alter/use them into doing so.
What I initially thought of was storing all possible combinations and them (randomly) picking k of them. However, that easily runs into memory issues...
Cheers
  1 Comment
Christos Saragiotis
Christos Saragiotis on 4 Aug 2017
If you have memory problems, then loop over it:
n = 10; p = 3; k = 12;
K = zeros(k,p);
i = 0;
while i<k
K(i+1,:) = sort(randperm(n,p));
i = i + 1;
if i==k
K = unique(K,'rows','stable');
i = size(K,1);
K = [K;zeros(k-i,p)];
end
end

Sign in to comment.

Answers (5)

Torsten
Torsten on 13 Jan 2016
Edited: Torsten on 13 Jan 2016
Look at the second block of code under
Build a second matrix combsubset_sorted which consists of the sorted (1xp) vectors obtained from "randi".
After generating a new vector of size (1xp) with randi, sort it and compare if it is already contained as a row in combsubset_sorted. If not, add the sorted vector to the matrix combsubset_sorted and the unsorted vector to the matrix combsubset.
Best wishes
Torsten.
  4 Comments
Torsten
Torsten on 13 Jan 2016
Did you look at the code provided in the link ?
You must build up the complete matrix row by row and check in each step whether the matrix already contains the actual permutation provided by randperm (maybe in a different order). That's why the matrix of sorted random vectors comes into play.
Best wishes
Torsten.

Sign in to comment.


Image Analyst
Image Analyst on 13 Jan 2016
Not sure why randperm() won't do it, but if you're looking for alternatives, look at randsample() and datasample() in the Statistics and Machine Learning Toolbox.
  3 Comments
Eric Schols
Eric Schols on 13 Jan 2016
When I said It might very well do it, but I don't see how, I was referring to randperm(), as were you in your original answer. The problem is that it outputs 1 row, where it should output multiple. The same goes for datasample and randsample....

Sign in to comment.


Image Analyst
Image Analyst on 13 Jan 2016
Edited: Image Analyst on 14 Jan 2016
I think I know what you want now (now that I've read your question more thoroughly). I believe you can get this done with randi() and unique(). See the following code:
N = 10 % Max integer value the data can have.
k = 40 % Number of rows you want in the final output
p = 3 % Number of columns
% Make a k-by-p array of values from 1 to N
% Make more rows than we need because we may throw out some if they're duplicates.
rows = 5 * k;
data = randi(N, rows, p)
% Get the list of rows all scrambled up
uniqueRows = unique(data, 'rows', 'stable')
% Extract the first N rows.
output = uniqueRows(1:N,:);
  5 Comments
Image Analyst
Image Analyst on 14 Jan 2016
This works. First it takes the data and gets rid of any rows with repeated numbers, like a row that = [1, 1, 4]. Then it takes the remaining data, sorts by column row-by-row, then uses unique() to toss out duplicate rows, then "unsorts" the columns on a row-by-row basis back to their original incoming locations:
N = 10 % Max integer value the data can have.
k = 40 % Number of rows you want in the final output
p = 3 % Number of columns
% Make a k-by-p array of values from 1 to N
% Make more rows than we need because we may throw out some if they're duplicates.
rows = 5 * k;
data = randi(N, rows, p)
% Now we have sample data, and we can begin.....
% First go down row-by-row throwing out any lines with duplicated numbers like [1, 1, 4]
goodRows = []; % Keep track of good rows.
% Bad rows will have unique() be less than the number of elements in the row.
for row = 1 : rows
thisRow = data(row, :);
if length(unique(thisRow)) == length(thisRow)
goodRows = [goodRows, row];
end
end
if ~isempty(goodRows)
data = data(goodRows,:);
end
% Sort row-by-row with columns going in ascending order
[sortedData, sortIndexes] = sort(data, 2);
% Get the list of rows all scrambled up
[uniqueRows, ia, ic] = unique(data, 'rows', 'stable')
% ia is the rows from A that we kept (extracted and stored in uniqueRows).
% Extract those same rows from sortIndexes so we know how to "unsort" the rows
sortIndexes2 = sortIndexes(ia,:);
% Extract the first N rows.
sortedOutput = uniqueRows(1:N,:);
% Now "unsort" them if you want to do that.
for row = 1 : size(sortedOutput, 1)
output(row,:) = sortedOutput(row, sortIndexes2(row, :));
end
output % Print to command window.

Sign in to comment.


Guillaume
Guillaume on 14 Jan 2016
Assuming k << nchoosek(N, p), I would just generate random combinations until you have k distinct ones:
function c = subsetcombs(v, k, p)
%v vector to pick from
%k number of combinations to return
%p number of elements to pick in each combination
N = numel(v);
assert(k <= nchoosek(N, p), 'You''ve requested more unique combinations than exist');
c = zeros(k, p);
for cidx = 1:k
while true
c(cidx, :) = v(randperm(N, p)); %generate random combination
if ~any(arrayfun(@(row) isempty(setdiff(c(row, :), c(cidx, :))), 1:cidx-1))
%no duplicate, move onto next cidx
break;
end
%duplicate combination, try another one
end
end
end
If k is close to the total number of combinations, then using nchoosek to generate all, and randperm to select a subset would be more efficient.
  3 Comments
Torsten
Torsten on 15 Jan 2016
Ah, "setdiff" instead of "diff" - that's tricky.
Best wishes
Torsten.

Sign in to comment.


Shlomo Geva
Shlomo Geva on 4 Dec 2020
Edited: Shlomo Geva on 4 Dec 2020
You can get this as follows:
1. First generate all binary vectors of size 2^N
n=dec2bin(0:2^N-1)-'0';
in the exampllle on hand, N is 10, so you that generates a matrix of 1024 binary row vectors
i.e
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1
...
1 1 1 1 1 1 1 1 1 1
2. Now remove all binary vectors that do not have exactly p ones
n(sum(n')~=p:)=[];
in the example above p is 4, and this leaves 210 binary row vectors, all of which have 4 ones set.
i.e.
0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 1 0 1 1
...
0 1 0 1 0 1 1 0 0 0
...
1 1 1 1 0 0 0 0 0 0
3. The positions of 1's in any of these row vectors are your desired unique combinations. You may collect any number of those 210 vectors as you like. They are all unique. To pick one just use the find function:
e.g. try this
>> find(n(1,:))
ans =
7 8 9 10
>>
>> find(n(120,:))
ans =
2 3 5 6
>>

Community Treasure Hunt

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

Start Hunting!

Translated by