Algorithm for Determining Variations of Differing Lengths

Question

I have four objects - for the sake of arguments, let say that they are the following letters: A B C D

I need to calculate the number of variations that can be made for these under the following two conditions:

1. No repetition
2. Objects are position agnostic

Taking the above, this means that with a four object sequence, I can have only one sequence that matches the criteria (since order is not considered for being unique):

• ABCD

There are four variations for a three object combination from the four object pool:

• ABC, ABD, ACD, and BCD

There are six variations for a two object combination from the four object pool:

• AB, AC, AD, BC, BD, and CD

And the most simple one, if taken on at a time:

• A, B, C, and D

I swear that this was something covered in school, many, many years ago - and probably forgotten since I didn't think I would use it. :-) I am anticipating that factorials will come into play, but just trying to force an equation is not working.

Any advice would be appreciated.

Answer 1

What you are thinking of is called a combination, and the number of combinations k in a group of n items is

n!/((n-k)!k!)

It is common to say "n choose k" when referring to the number of combinations, as you are essentially "choosing" k elements from n.

EDIT: Ah, I misread a bit. You want the count of all possible combinations, essentially sum(nCk, k = 0 to n). This is the power set and is 2^n (or 2^n - 1 if you don't want to count the empty set).

Answer 2

There are 2^n combinations of n objects, where each object can either be (in the set) or (not in the set). So you can think of each combination in the set of combinations as one integer in the range (0, (2^n-1)).

To get every combination, just iterate over this range and treat each integer as a bitmask. For every 1 bit in the integer, the corresponding element belongs in the set.

Aside: this is called a power set.