0
$\begingroup$

Edit: The mistake was in me counting (enumerating by hand) which @JMoravitz kindly taught me to do right in the chat. Apologies!

I'm trying to code a problem I have, and I would like to use a combination approach. But I seem to make the wrong assumptions, or I cannot calculate right (which is reasonably plausible).

If I have, n elements and I pick $\frac n2$ elements, I thought the number of combinations I get should be n choose $\frac n2$ ?

For example 4 elements gives 6 combinations. And 6 elements give 20 combinations.

So if I have elements a b c d I can have:

a b x x or

a x c x or

a x x d or

x b c x or

x b x d

total of 6.

If I do this for 6 elements a b c d e f

a b c x x x

a b x d x x

....

x b c d x x

x b c x e x

.....

x x x d e f

And count them I am getting a total of 16 combinations? Am I missing some with this method? If not (though possible, I went over it numerous times already), how do I calculate the right number of combinations?

Thank you for your help.

$\endgroup$
6
  • 1
    $\begingroup$ In general, the number of ways of selecting $k$ objects out of $n$ objects total will be $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$. In your case, you just use $k=\frac{n}{2}$, giving the central binomial coefficients. In general it is a terrible idea to list them all out and brute force the count. In the case of $n=6$ that is $\binom{6}{3}=\frac{6!}{3!3!}=20$. Had you brute forced and listed them all out you should have also gotten $20$, so you must have missed some if you only counted $16$, the problem with trying to manually count $\endgroup$
    – JMoravitz
    Commented Nov 15, 2019 at 16:46
  • $\begingroup$ hello @JMoravitz thank you! would you know if the method I use to get the combinations with shifting the index doesn't get you all the combinations? $\endgroup$
    – oliver
    Commented Nov 15, 2019 at 16:51
  • 1
    $\begingroup$ As for coding this... that gets a bit off topic, but you can use three nested for loops, each index corresponding to which position in your string should be the usual letter versus an x. Pseudo code being: basestr = "xxxxxx"; for i in [1..6] { for j in [(i+1)..6] { for k in [(j+1)..6] { result = basestr; result[i]=i; result[j]=j; result[k]=k; print(result) } } }. Adjust the code for your prefered language. All combinations will be generated, none missed. Note that $\sum\limits_{i=1}^6\sum\limits_{j=i+1}^6\sum\limits_{k=j+1}^6 1 = \binom{6}{3}=20$. $\endgroup$
    – JMoravitz
    Commented Nov 15, 2019 at 16:54
  • $\begingroup$ thanks @JMoravitz this is exactly how I coded this, three nested loops. but because I calculated 20 combinations I'm thinking something is wrong. I wrote it out by hand and got 16 and by code as well. I've been looking at these 16 for 45 minutes haha. I cannot find the missing 4. So I figured my math is wrong. $\endgroup$
    – oliver
    Commented Nov 15, 2019 at 16:57
  • 2
    $\begingroup$ If you share the list and/or the code, we might be able to point out what went wrong, but in terms of the mathematics of your question, again, there will be $\binom{6}{3}=20$ combinations. As a guess, perhaps you hardcoded a limit on the highest that $i$ could go too low. There are exactly four outcomes where $i$ occurs in the third position or later. That would have had you miss xxcdex, xxcdxf, xxcxef, xxxdef $\endgroup$
    – JMoravitz
    Commented Nov 15, 2019 at 17:00

1 Answer 1

Reset to default
1
$\begingroup$

Summarizing the chat and comments above, there are in general $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$ ways to choose $k$ elements out of $n$. For the special case of $k=n/2$ these are the Central Binomial Coefficients.

Following the pattern begun in the list above and taking it all the way, we arrive at a pseudocode for generating the list as simply looping over three indices (or $n/2$ indices in general), at each nested loop starting the index at one higher than the current index of the loop it is in.

Some dirty javascript code accomplishing this for the case of $n=6$: for (i=0; i<6; i++){ for (j=i+1; j<6; j++){ for (k=j+1; k<6; k++){ resultstr = ""; for(l=0; l<6; l++){resultstr+=l==i||l==j||l==k?l:"x"}console.log(resultstr)}}}

This particular order in which we listed the combinations is of particular interest and is what we call the lexicographic order of the combinations. Had we listed them without the X's, your list is abc, abd, abe, abf, acd, ace, acf, ..., def. The lexicographic order of these is then simply the "dictionary order", just as you would have expected to see these arranged in the dictionary.

As for what went wrong with your earlier code, perhaps some gremlins played a trick on you, but when going to verify the code it was correct and got the expected result.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .