# k distinct combinations of size p without replacement

38 views (last 30 days)

Show older comments

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
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

### Answers (5)

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
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.

Image Analyst
on 13 Jan 2016

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
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.

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

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

>>

##### 0 Comments

### See Also

### Community Treasure Hunt

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

Start Hunting!