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

13 vues (au cours des 30 derniers jours)
JT
JT le 29 Mar 2016
Commenté : Paul Smits le 29 Avr 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?

Réponses (4)

Paul Smits
Paul Smits le 26 Avr 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.
  1 commentaire
Jan
Jan le 28 Avr 2019
Modifié(e) : Jan le 29 Avr 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.

Connectez-vous pour commenter.


Jos (10584)
Jos (10584) le 28 Avr 2019
Modifié(e) : Jos (10584) le 28 Avr 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 commentaires
Jos (10584)
Jos (10584) le 29 Avr 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).

Connectez-vous pour commenter.


Jan
Jan le 26 Avr 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 commentaires
Paul Smits
Paul Smits le 26 Avr 2019
Uses v values directly as an indices in t(v(k, :)). Only works for input 1:m.
Jan
Jan le 28 Avr 2019
@Paul Smits: Yes, but it is trivial to expand this:
data = rand(1, 10);
... % my code
vdata = data(v);
wdata = data(w);

Connectez-vous pour commenter.


Paul Smits
Paul Smits le 26 Avr 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.

Catégories

En savoir plus sur Get Started with MATLAB dans Help Center et File Exchange

Tags

Produits

Community Treasure Hunt

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

Start Hunting!

Translated by