k distinct combinations of size p without replacement

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

[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

Answer 1

[Torsten]

Look at the second block of code under

http://stackoverflow.com/questions/8157554/randomly-select-subset-of-all-possible-combinations-in-matlab

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.

[Eric Schols]

But randi does it with replacement, doesn't it?

C = randi(N,[k p])

doesn't prevent from seeing every entry of C being 1, for example...

[Torsten]

Then use "randperm(N,p)" instead of "randi".

Best wishes

Torsten.

[Eric Schols]

I don't see how that will work, as "randperm(N,p)" outputs only 1 row. Could you give an example in code?

[Torsten]

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.

Answer 2

[Image Analyst]

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.

[Eric Schols]

It might very well do it, but I don't see how. Hence, I asked for an example :)

[Image Analyst]

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]

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

Answer 3

[Image Analyst]

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,:);

[Torsten]

1. randperm instead of randi has to be used.

2. You don't throw away rows that are permutations of each other . E.g. [1 4 9] and [1 9 4] are considered equal. So sorting should be used to find these rows.

Best wishes

Torsten.

[Image Analyst]

#1 is not true. Just look at the original post where numbers are repeated. randperm() does not repeat numbers. Even on a row by row basis there is a possibility of repeated numbers because he says that there is a possibility of something like [1 1 4] which he wants filtered out.

#2 is correct. To handle permutations of the same 3 numbers, the rows would have to be sorted before calling unique to throw out repeats. Then the rows would have to be put back in the original order.

If [1 1 4] is in there, my code above does not filter that out since it's not the same as another row. You'd have to call unique on each row and throw out any results that are not the full number of columns.

I'll see if I can post a fix for these two things later.

[Torsten]

#1 No repetitions in rows are allowed.

Best wishes

Torsten.

[Image Analyst]

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]

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.

Answer 4

[Guillaume]

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.

[Torsten]

Does the if-statement consider [1 9 4] and [1 4 9], e.g., as equal, as intended by the OP ?

Best wishes

Torsten.

[Guillaume]

Yes, it does. That's the whole point of it.

[Torsten]

Ah, "setdiff" instead of "diff" - that's tricky.

Best wishes

Torsten.

Answer 5

[Shlomo Geva]

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

>>