How to encode a linear ordering of elements efficiently? I wish to encode the linear ordering of elements, say $\{a, b,c,d,\ldots\}$, into as brief a description as possible to enumerate them efficiently. Only the relative position of all pairs of elements is important, e.g. whether $a$ is left/right of $b$ and so on.
I was thinking of logical variables: whether an element is right of another or not. For example, $x_{a,b}=1$ would mean that $b$ is right of $a$ in the order. However, some combinations are impossible. For example, $x_{a,b}=1$, $x_{b,c}=1$, and $x_{a,c}=0$ are contradictory.
Therefore, it would be good to have a description that produces only possible orderings.
 A: Since there are $n!$ possible orderings, the description of such an ordering must have a length of at least $\Omega(\log(n!)) = \Omega(n \log(n))$. If you have $n$ variables $v_1, \ldots, v_n$, then specifying a variable $v_i$ by its index $i$ should require $\lceil \log_2(n) \rceil$ bits, so simply writing down the sequence of $n$ indices of the linear ordering of the variables $v_i$ is already asymptotically optimal (up to a constant). This is a bit better than the description you give, where you have to store a bit for each pair $(v_i, v_j)$ for $n^2$ bits total.
If you actually want to generate descriptions of these orders efficiently and quickly, then something like this might be convenient: a description of a linear order on $\{v_1, \ldots, v_n\}$ starts with an index $1 \leq k \leq n$, which is the first element in the ordering. That leaves the $n-1$ element set $\{v_1, \ldots, v_{k-1}, v_{k+1}, \ldots, v_n\}$. Then simply use the same recipe to give a description for this set, i.e. you next give an index between $1$ and $n-1$. (Note that the indices at each step do not refer to the same element.) A description of a linear ordering of $\{v_1, \ldots, v_n\}$ then becomes a list of numbers $k_1, \ldots, k_n$ where $1 \leq k_i \leq n - i + 1$, and each such list corresponds to precisely one ordering.
