I'm familiar with the formula to figure out how many non-repeating combinations there are in an n choose r situation, but I was wondering what would be the simplest pattern to go about writing all of those combinations on paper methodically, without the use of a computer.
I tried an 8 choose 4 scenario of the letters A-H, writing out each combo on an Excel spreadsheet going down a line each time. This was the general pattern:
Start with ABC and do D-H as the 4th. Increment C to D; do ABD and do E-H as the 4th. ABE + F-H. ABF + G-H. ABG + H.
Increment B to C, so
ACD + E-H. ACE + F-H. ACF + G-H. ACG + H.
Increment C to D, so
ADE + F-H. ADF + G-H. ADG + H.
And so on, incrementing the 4th, 3rd, 2nd, and 1st "digits" as though they were numbers, but following the rule that the 4-letter combos are always in alphabetical order (so as not to repeat any combo), until I get to EFGH.
So I figure the algorithm is pretty much the same for any N choose R scenario: 1. Put the superset of N items in some kind of order, 2. Start with the first R-1 items, and combine them with all of the remaining items, one at a time, as the Rth digit, 3. Increment the "digits" as you would if counting ordinary integers, i.e., when you get to the Nth item in the superset, reset that digit place and increment the digit place to the left, 4. Following the rule that in your combos, no item is repeated, and no item is to the left of another unless it's also to left of it in the order you created for the superset in step 1 5. Your final sequence should be the last R items of your superset.
Is this a generally sound algorithm (assuming of course that R <= N)?
