Index Lists

Why

We want language and notation for selecting some of the entries (possibly, with reordering—i.e. permuting) from a list.

Definition

An index list of order $n$ and length $r \leq n$ is a list of distinct elements of $\upto{n}$. Its $i$-index is the $i$th coordinate, where $i = 1, \dots , r$.

Examples

Here are some index lists of order 5: $(1,2,3)$, $(3,2,1)$, $(4,5,1)$, $(5,4,3,2,1)$, $(3,)$. These have lengths 3, 3, 3, 7 and 1, respectively. The $3$-index of the first is 3, and of the second is 1.

Induced sublist

The sublist of an length-$n$ list $x$ induced by a length-$r$ index list $\alpha $ is the length-$r$ list $y$ whose $i$th entry is the value $x_{\alpha _i}$. In other words,

\[ y_i = x_{\alpha _i} \]

For example, define $x = (6, 4, 5, 3, 9)$. The sublists associated with the example index lists above are $(6, 4, 5)$, $(5, 4, 6)$, $(3, 9, 6)$, $(9, 3, 5, 4, 6)$ and $(5,)$.

For a particular case, the third holds because

\[ (3, 9, 6) = (x_4, x_5, x_1)= (x_{\alpha _1}, x_{\alpha _2}, x_{\alpha _3}) \]

Notation

We denote the induced sublist of list $x$ induced by index list $\alpha $ by $x_\alpha $. This is a slight abuse of notation, since we have so far defined a list with a subscript symbol mean the subscript-symbol term of that list. This ambiguity is avoided in our discussion if we keep in mind the types of the objects.

Index sets

An index set $S \subset {1,\dots ,n}$ can be associated with an index list in a natural way. It corresponds to the length-$\num{S}$ index list which has the elements of $S$ in their natural order. We denote the induced sublist by $x_S$.