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

Question

JT on 29 Mar 2016

0

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?

1 Comment

Jos (10584) on 28 Apr 2019

yes, rather easy: use nchoosek(1:n, n-k) and flip the output

Sign in to comment.

Sign in to answer this question.

Answer 1

Paul Smits on 26 Apr 2019

2
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#answer_372473

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.

1 Comment

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.

Answer 2

Jos (10584) on 28 Apr 2019

2
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#answer_372682

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!

3 Comments

Jan on 29 Apr 2019

+1. Nice and neat. The order of outputs of nchoosek is not documented, so it is worth to include this test in the unit-tests of the function, such that it can be checked for each Matlab release the code is running on.

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

Paul Smits on 29 Apr 2019

Excellent!

Sign in to comment.

Answer 3

Jan on 26 Apr 2019

0
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#answer_372442

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

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.

Answer 4

Paul Smits on 26 Apr 2019

0
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/276055-how-can-i-use-nchoosek-to-output-both-the-k-combinations-and-the-remaining-combinations#answer_372471

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.

1 Comment

Jan on 29 Apr 2019

Of course creating all permutations at first requires a lot of RAM.

Sign in to comment.

You are now following this question

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

1 Comment

Answers (4)

1 Comment

3 Comments

2 Comments

1 Comment

See Also

Categories

Tags

Products

Community Treasure Hunt

Tags

Products

See Also

Community Treasure Hunt

You are now following this question

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

1 Comment

Answers (4)

1 Comment

3 Comments

2 Comments

1 Comment

See Also

Categories

Tags

Products

Community Treasure Hunt

Tags

Products

See Also

Community Treasure Hunt

An Error Occurred

WeChat