Efficiently mapping a finite powerset into the first n natural numbers? Say I have a finite set $S$, where $|S| = n$. How would I efficiently map $\mathcal{P}(S)$ to $0, 1, \ldots 2^n$?
For example, let $S = \{0, 1, 2\}$ and $\mathcal{P}(S) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\}$. Is there a way to map $\emptyset \rightarrow 0$, $\{0\} \rightarrow 1$, $\ldots \{0,1,2\} \rightarrow 7$? While it seems almost trivial at first, it gets complicated when $n$ grows. For simplicity, we can assume that $S = \{0, 1, \ldots ,n\}$ for $|S| = n$.
Just to clarify, I'm looking for a mapping that depends only on the current subset. My only solution has been to count off each subset of the same size and adding the binomial coefficients. If I want to find the position of $\{1,2\}$, which has size $k = 2$, I count up from $\{0,1\}$ which gives me $2$, and add $\sum_{i = 0}^{k - 1}{n\choose{i}}$.
For sufficiently large $n$, the "counting up" takes longer than $O(n)$ since it grows with the size of $n\choose{n/2}$. I'm assuming there's a better method than the one I put together but I can't seem to find one. Any tips/references are greatly appreciated!
EDIT: It's very important that smaller subsets come before larger subsets when ordered. $\{5\}$ should be mapped to a lower number than $\{2,4\}$.
 A: Well, we can't embed $\mathcal P(S)$ into $\{0,1, \ldots, n \}$, because $\mathcal P(S)$ has $2^{|S|}= 2^n$ many elements, but there is a canonical embedding $\mathcal P(S) \to \{0,1, \ldots, 2^{n} \}$:
Fix an enumeration $S = \{s_{0}, \ldots, s_{n-1} \}$ (all the $s_{i}$ are distinct). Given any subset $A \subseteq S$ let 
$$
\chi_{A} \colon \{0, \ldots, n-1 \} \mapsto \{0,1\}, i \mapsto \begin{cases}
1 & \text{, if } s_{i} \in A \\
0 & \text{, otherwise}
\end{cases}.
$$
Then 
$$
\pi \colon \mathcal P(S) \to \{0,1, \ldots, 2^{n}-1\}, A \mapsto \sum_{i=0}^{n-1} \chi_{A}(i) \cdot 2^{i}
$$
is an injection (and in fact a bijection).

In a comment @m1ckey requested an additional property that I'd interpret as follows: Let $S = \{1, 2, \ldots, n\}$. Find a bijcetion $\psi \colon \mathcal P(S) \to \{0,1, \ldots, 2^{n}-1 \}$ such that for all  subsets $A,B \subseteq S$ with $\max (A) < \max (B)$ we have $\psi(A) < \psi(B)$. (Please let me know if that's what you are asking for.) Such a bijection is possible: Let $\prec \subseteq \mathcal P(S) \times \mathcal P(S)$ be such that for all $A,B \subseteq S$:
$$
A \prec B \text{ iff } (A \neq B \text{ and } \max(A \Delta B) \in B),
$$
where $A \Delta B = (A \setminus B) \cup (B \setminus A)$ is the symmetric difference of $A$ and $B$. Note that $A \prec B$ iff $A \neq B$ and $B$ contains the element largest element $i \in \{1, \ldots, n\}$ that appears in exactly one of $A$ and $B$.
Note also that $\prec$ is transitive, irreflexive and (strictly) total. Hence there is a unique enumeration $\{X_{i} \mid i \in \{0,1, \ldots, 2^{n}-1 \} \}$ of distinct subsets $X_{i} \subseteq S$ such that
$$
X_{0} \prec X_{1} \prec \ldots \prec X_{2^{n}-1}.
$$
Now define
$$
\psi \colon \mathcal P(S) \to \{0,1, \ldots, 2^{n}-1 \}, X_{i} \mapsto i.
$$
This has the desired property (it actually has a stronger such property, namely that the same holds for all initial segments on both sides). 
Let me give some values of $\psi$. It's easy to see that either I made a foolish mistake in my calculations or $\psi(\emptyset) = 0$, $\psi(\{ 1 \}) = 1$, $\psi(\{ 2 \}) = 2$, $\psi(\{ 1, 2 \}) = 3$, $\ldots$, $\psi(\{2, \ldots, n\}) = 2^{n}-2$, $\psi(\{1, \ldots, n \}) = 2^{n}-1$.
A: Suppose you had the set $A = \{a_{1},\ldots,a_{n}\}$, then each element of $\mathcal{P}(A)$ either contains $a_{i}$ or it does not. So each element of $\mathcal{P}(A)$ can be mapped to a binary string such as $0010101110101$ where a $1$ in the $i^{\text{th}}$ position means the element contains $a_{i}$. These binary strings can then be converted into base $10$ notation.
A: I find the more natural way to built the powerset of a given set $A = \{a_{1},\ldots,a_{n}\}$ is listing all numbers from $0$ to $2^n$ as a binary number of lenght n, and reading from right to left:

*

*0...0000 (nothing)

*0...0001 (take the first, {$a_{1}$} )

*0...0010 (take the second, {$a_{2}$} )

*0...0011 (take the first and the second, {$a_{1}$,$a_{2}$})

*0...0100 (take the third, {$a_{3}$})

*0...0101 (take the first and the third, {$a_{1}$,$a_{3}$})

...
