k distinct combinations of size p without replacement

15 次查看(过去 30 天)
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 个评论
Christos Saragiotis
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

请先登录,再进行评论。

回答(5 个)

Torsten
Torsten 2016-1-13
编辑:Torsten 2016-1-13
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 个评论
Eric Schols
Eric Schols 2016-1-13
I don't see how that will work, as "randperm(N,p)" outputs only 1 row. Could you give an example in code?
Torsten
Torsten 2016-1-13
编辑:Torsten 2016-1-13
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.

请先登录,再进行评论。


Image Analyst
Image Analyst 2016-1-13
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 个评论
Image Analyst
Image Analyst 2016-1-13
Perhaps you didn't scroll down far enough in the help to see the section called "Examples". Try that.
datasample
Randomly sample from data, with or without replacement
randsample:
y = randsample(n,k) returns a k-by-1 vector y of values sampled uniformly at random, without replacement, from the integers 1 to n.
Each one of those functions has several examples.
Eric Schols
Eric Schols 2016-1-13
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....

请先登录,再进行评论。


Image Analyst
Image Analyst 2016-1-13
编辑:Image Analyst 2016-1-14
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 个评论
Image Analyst
Image Analyst 2016-1-14
Right, in the output. So if you had input data with [1 1 4] (which he mentions as a possibility), he wants that filtered out so that it's not in the output.
Image Analyst
Image Analyst 2016-1-14
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.

请先登录,再进行评论。


Guillaume
Guillaume 2016-1-14
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 个评论
Torsten
Torsten 2016-1-15
Ah, "setdiff" instead of "diff" - that's tricky.
Best wishes
Torsten.

请先登录,再进行评论。


Shlomo Geva
Shlomo Geva 2020-12-4
编辑:Shlomo Geva 2020-12-4
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
>>

类别

Help CenterFile Exchange 中查找有关 Matrices and Arrays 的更多信息

Community Treasure Hunt

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

Start Hunting!

Translated by