Subsets - Ranking / Unranking

Question

I am looking at the following codes:

It is lexicographic order related to ranking and unranking.

Here is also an example:

There is also the Gray code:

with the repective examples:

I haven't really understood the ranking and the unranking.

So we have a set and we want to find all the subsets either with the lexicographic oder or with Gray code and then we search for a specific subset and the position is the rank?

$$$$

EDIT:

The subset $T \subseteq S$ can de described by the vector $x(T)$ of length $n$ where at each position there is $1$ if the respective element is contained, $0$ else.

As for Gray Code : It is defined recursively as follows. We start with $G^1=[0,1]$. in each of the next levels we take the previous one with a $0$ at the beginning and we add the previous one reversely with $1$ at the beginning, e.g. $G^2=[00,01,11,10]$, etc.

For the algorithms ranking and unranking we consider the relation between Gray Code and the binary representation.

The bits $b_i$ of Gray Code is $1$ if at the binary representation the bits $b_i$ and $b_{i+1}$ are different.

For the ranking we take the bits from the most important to the less important and where the respective element that we check contains in the subset we reverse the bit b (initially $0$). At each bit that is one we augment also the rank.

For the unranking we take the binary representation of rank and we add to the subset the elements for those that the consecutive bits were different.

Answer 1

Your question example is part of these lecture notes.

SubsetLexRank computes an integer $0 \dots 2^n-1$ which indicates which of the $n$ elements is contained in the subset.

This method is used in many programming languages to express Boolean flags in one integer. The $n$ elements of the set are assigned to single-bit numbers which are integer powers of two:

S1 - 1 = 2^0      binary 000...0001
S2 - 2 = 2^1      binary 000...0010
S3 - 4 = 2^2      binary 000...0100
...
Sn -   = 2^(n-1)  binary 100...0000

For $n$ elements of a set, there are $2^n$ ways to select a subset. Each selection can be expressed as $n$-bit binary number by adding up the numbers assigned to the selected elements.

If such $n$-bit binary number is given, method SubsetLexUnrank determines the subset which is represented by this number. The number is examined bit-by-bit. Whenever a bit is set, the respective set element is included in the subset.

The Lex methods simply increment the rank numbers in an arithmetic fashion. Subsequent ranks have difference of one.

The GrayCode methods order the rank numbers in such a way, that subsequent numbers are only different in one bit-position. Result is a different ordering of the subsets. Subsets which differ in one element are ordered in adjacent positions.

In GrayCodeRank, the loop variable $i$ is decremented from $n-1$ down to $0$. Starting from element $1$ to element $n$, the presence or selection state of a set element is tested. Whenever an element is found to be present in the subset, the Boolean variable $b$ is flipped between true and false. For true values of $b$, the respective bit is set in the rank variable $r$. Thus, the rank variable is a representation of selection changes. These changes can be re-played during unranking to retrieve the appropriate subset.

Gray code ranks for three elements:

subset	Gray code rank
{}	0
{3}	1
{2,3}	2
{2}	3
{1,2}	4
{1,2,3}	5
{1,3}	6
{1}	7

Note that subsets in adjacent rank positions $0 \dots 2^n-1$ differ in exactly one set element.

Summary:

The rank is a unique presentation of the set elements selected into the subset.
Unranking determines from a given rank, which elements are selected to be in the subset.