# Which is the algorithm to calc possible sets?

Example: I have a set {a,b,c}. I want to know how many different sets could I get from these elements. -Ex: {a,b} , {a,c} , {a}, {b} , {c} , {b,c} and {a,b,c} itself

Which is the algorithm ? and which theory is this?

-

Given a set with $n$ elements it has $2^n$ subsets, and $2^n-1$ non-empty subsets.

You can prove this by induction, in fact this is one of the standard examples for induction.

In your example you have $\{a,b,c\}$ which are $3$ elements, and therefore $2^3-1=7$ non-empty subsets.

-

You are "computing" the so-called powerset of the initial set. Each element (of the original set) can or cannot be chosen in a possible subset. If you start with $n$ elements that are $n$ yes/no choices, so $2^n$ possible subsets. That includes the all-no sequence of choices, or the emptyset $\varnothing$.

I guess that is the algorithm you want to have. If you know binary numbers, listing them is as listing subsets. In your example 000, 001, 010, 011, 100, \dots, 111 form $\varnothing$, $\{a\}$, $\{b\}$, $\{b,a\}$, $\{c\}$, $\{c,a\}$, $\{c,b\}$, $\{c,b,a\}$. Done. Silly order in the sets, but I wanted to stay close to the order I took for the bits: cab.

-