2
$\begingroup$

So, recently, I have found myself in the position of having to implement a combinations function in MATLAB. What I mean by this is the following: I simply need to list all possible combinations for an ${m \choose n}$ problem.

More concretely, lets say I am given an $m=4$ length vector, where its indicies increase from $1$ to $m$, (e.g. $[1, 2, 3, 4]$). Let us also say that in this example, $n = 2$. Thus, I want to find all ${4 \choose 2} = 6$ possible combinations, and I would like the routine to therefore spit out: $$\begin{bmatrix}1 & 2 \\1 & 3 \\ 1&4 \\2&3\\2&4\\3&4 \end{bmatrix} $$.

(The reason I need a list like that is because those numbers are going to be used as indicies of another matrix, but thats not important). Now, Ive googled around, and MATLAB has a function to do this, but I do not have it, as I dont have the stats toolbox. Be that as it may, I suppose I could sook something up, but I do not think that it would be too efficient, and worse still, it might not be generalizable for any $m$ or $n$.

I therefore would not mind writing my own routine, if it is not too involved, but I would like some help as to how this can be accomplished. Thanks!

$\endgroup$
2
$\begingroup$

You can find an implementation in Octave. The function is, as in Matlab, called nchoosek. Documentation is here. For the theory behind this type of algorithms, you can consult section 7.2.1 of Volume 4A of The Art Of Computer Programming by Donald Knuth.

$\endgroup$
  • $\begingroup$ I think you have misunderstood my question. I have nchoosek. I am trying to make a list of numbers, as that matrix shows, not figure out how to compute nchoosek. $\endgroup$ – Spacey Mar 12 '13 at 16:10
  • $\begingroup$ @Bateekha: aren't you looking for this: ´nchoosek (1:3, 2)´, i.e. give a vector to nchoosek as first argument so that it returns a list of all combinations? $\endgroup$ – GertVdE Mar 12 '13 at 16:12
  • $\begingroup$ @Bateekha: in your original post, you mention "MATLAB has a function to do this, but I do not have it"... That's why I pointed you to Octave. $\endgroup$ – GertVdE Mar 12 '13 at 16:16
  • 1
    $\begingroup$ >< You are correct. That is exactly what I need. >< $\endgroup$ – Spacey Mar 12 '13 at 16:16
  • $\begingroup$ I guess I do not understand how this works...is there a simple 'way' of going about computing it? (I am looking at the function). $\endgroup$ – Spacey Mar 12 '13 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.