Combinations

Combinations of a set are choices (subsets) of its elements. Order does not matter, so the combination {a,b,c} is considered the same as {a,c,b}. (For cases where order matters, see the previous page.)

Brief Explanation

This page constructs (as opposed to merely counting) the combinations for (modestly-sized) sets. It is a well-known result that for an N-element set, there are 2^N different combinations (subsets).

However, this fact does not tell you what those subsets are. In the next section you can list these subsets. The elements in the sets will always be the letters a, b, c, etc.

Try It Yourself

Each bulleted line finds one or more combinations, explained below. To calculate, enter the required numbers in the round text fields, and click the in the same line.

• The for  letters.  (Sort by size)
• The th  of the power set on  letters. (Zero-based.)
• (From N letters, choose k of them.)

Remarks

• The first bulleted line above calculates all the subsets of an N-element set — called the power set. This can be a very large list and a very time-consuming calculation. So if you enter a large value for N (larger than 12) you will be quizzed on whether you really mean it or not.

  In fact, the calculation proceeds very quickly — it is the text-processing, the unpacking of the result and rendering it into the Web page, that is vastly slower. Web pages are not necessarily the most efficient way to perform calculations. However, they can be very illustrative. And should you choose to try your own hand at generating these lists (using e.g. C or Python or Ruby or Lisp) you will have at least some small values to compare to.

  If you do not check the “Sort by size” box, the order you get is just the natural one that comes from the recursive code. If you check the box, the subsets are sorted from smallest to largest.

• The second line above calculates only a single combination, which is of course a much faster calculation. This is called a generator function. If you need to run through all combinations and do something with each one, you may not want to pre-calculate them all first — that could take up a lot of space. Instead, just step through the combinations by calling the generator repeatedly.

  The order used by this generator is the same “natural” one used to find the complete power set. The farthest you can go with this generator is the 67108863-rd element of the power set on 26 letters. Check it out.

• The third line finds a subset of the power set: those with k elements. (Called “N choose k” or “C(N,k)” in the literature.) The size of this subset is strongly connected with the binomial coefficients and Pascal’s triangle.

The code I am using is all visible: just do a “View Page Source” or its equivalent on this Web page.

The next page ... does not yet exist. But I have so many ideas I don’t know where to begin!