25 views (last 30 days)

I would like to run the nchoosek function and return all the k combinations as a matrix (which I can do already) but also the relavent remaining values in a separate matrix. A splitting process of all the values based on the k value.

For example if I nchoosek (where n=10 and k=4) it would output all combinations of 4 values in one matrix and all the remaining 6 values in another matrix.

Is this possible?

Paul Smits
on 26 Apr 2019

Fastest solution so far is my rahter clumsy attempt at using logical indexing to solve the problem:

m = 10;

n = 4;

b = nchoosek(m,n);

ii = true(m,b);

ii(nchoosek(1:m,n)'+(0:m:m*b-1))=false;

xr = repmat([1:m]',1,b);

v = reshape(xr(~ii),n,b)';

w = reshape(xr(ii),m-n,b)';

Readability can be improved upon. But definitely fast.

Note that this method can also take input other than 1:m:

x = [8 8 8 6 1 2 3 4 10 4]; %other input

n = 4;

m = size(x,2);

b = nchoosek(m,n);

ii = true(m,b);

ii(nchoosek(1:m,n)'+(0:m:m*b-1))=false;

xr = repmat(x',1,b);

v = reshape(xr(~ii),n,b)';

w = reshape(xr(ii),m-n,b)';

Sidenote: A possibility for nchoosek to output remaining values directly would be quite a nice feature.

Jan
on 28 Apr 2019

+1. If speed matters, you could modify https://www.mathworks.com/matlabcentral/fileexchange/26190-vchoosek

I've posted a method, which avoid the 3 transpositions. I've tried to test it in Matlab Online without success for 15 minutes: Either the editing does not work, pressing the backspace key deletes the window, hitting Ctrl-Return executes one line only and not the complete code, etc. I gave up. Matlab Online is not working reliably. What a pity.

Sign in to comment.

Jos (10584)
on 28 Apr 2019

Edited: Jos (10584)
on 28 Apr 2019

The remaining values can simply be obtained using nchoosek(1:n, n-k), you just have to flip the order of the output :-)

n = 7

k = 2

A = nchoosek(1:n, k)

remainingValues = flipud(nchoosek(1:n, n-k))

% a check that the combination contains all numbers

tf = sort([A remainingValues],2) == 1:n ;

all(tf(:)) % TRUE!

Jan
on 29 Apr 2019

Jos (10584)
on 29 Apr 2019

Thanks Jan :-)

You're right that the order is not documentd, but yet I think that for any decent algorithm the order of the output should not depend on K, so that nchoosek(1:N, K) and nchoosek(1:N, N-K) have to be symmetrical, in the sense that, for instance, [1 2 ... K] and [1 2 ... N-K] occupy the same row in both outputs (in my version row 1).

Sign in to comment.

Jan
on 26 Apr 2019

% The loop version:

m = 10;

n = 4;

v = nchoosek(1:m, n);

nv = size(v, 1);

w = zeros(nv, m - n);

for k = 1:nv

t = 1:m;

t(v(k, :)) = [];

w(k, :) = t;

end

There must be a non-loop version also, but it will need larger temporary arrays.

Paul Smits
on 26 Apr 2019

Uses v values directly as an indices in t(v(k, :)). Only works for input 1:m.

Jan
on 28 Apr 2019

@Paul Smits: Yes, but it is trivial to expand this:

data = rand(1, 10);

... % my code

vdata = data(v);

wdata = data(w);

Sign in to comment.

Paul Smits
on 26 Apr 2019

I tried a way without loops, using perms instead of nchoosek:

m = 10;

n = 4;

per = perms(1:m);

[v,iper,~]= unique(sort(per(:,1:n),2),'rows');

w = sort(per(iper,n+1:end),2);

Albeit shorter, this is significantly slower than Jan's solution. Gets real slow for m of 9 or higher.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 1 Comment

## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#comment_699288

⋮## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#comment_699288

Sign in to comment.