# How can i use nchoosek to output both the k combinations and the remaining combinations?

9 views (last 30 days)
JT on 29 Mar 2016
Commented: Paul Smits on 29 Apr 2019
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?
Jos (10584) on 28 Apr 2019
yes, rather easy: use nchoosek(1:n, n-k) and flip the output

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

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!
Paul Smits on 29 Apr 2019
Excellent!

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.
##### 2 CommentsShowHide 1 older comment
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);

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.
Jan on 29 Apr 2019
Of course creating all permutations at first requires a lot of RAM.