Standardnummerierung

Die Standardnummerierung der abzählbar-unendlichen Menge der Zeichenketten <math>\Sigma^*</math> ist die unter den Voraussetzungen eines beliebigen Alphabetes <math>\Sigma:=\{\sigma_1\ldots\sigma_m\}</math> mit endlicher Mächtigkeit <math>m:=|\Sigma|\in\mathbb{N}</math> und eindeutiger Zeichennummerierung <math>\sigma \in \Sigma^{\{1\ldots m\}}</math> (wo die Zahlen <math>1\le i\le m</math> den Gesamtvorrat aller Zeichen <math>\sigma_i\in\Sigma</math> produzieren) diejenige Aufzählweise <math> \nu_\sigma \in (\Sigma^*)^{\mathbb{N}} </math> (wo jede Zahl <math>n\in\mathbb N</math> genau ein Wort <math>\nu_\sigma^n \in \Sigma^*</math> produziert), welche genau diejenige bijektive Aufzählbarkeit <math> \alpha_\sigma\in \mathbb N^{\Sigma^*} </math> (wo jede möglichen Zeichenkette <math>w\in\Sigma^*</math> genau eine Zahl <math>\alpha_\sigma^w\in\mathbb N</math> produziert) umkehrt, die für alle Worte <math> \sigma_{i_1}\ldots\sigma_{i_L}\in\Sigma^{2+} </math>jedweder Länge <math>L\in\mathbb N</math> der optimalen Konvention gehorcht, dass

<math> \alpha_\sigma^{\sigma_{i_1}\ldots\sigma_{i_L}}=\sum_{p=1}^L i_p m^{L-p} </math>

Beispiele

Binäre Standardnummerierung mit Haskell

Sei <math>\Sigma = \{1,2\}</math> mit <math>(1,2)=(\sigma_1,\sigma_2)</math>.

Die Elemente der Menge <math>\Sigma^*</math> lassen sich systematisch auflisten:

<math>\Sigma^*=\{\epsilon, 1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222, \ldots\}</math>

Als i-tes Wort in der Liste erscheint stets <math>\nu_\sigma^i</math>.

<math>\nu_\Sigma^8=112</math> entspricht <math>\alpha_\sigma^{112} = \alpha_\sigma^{\sigma_1\sigma_1\sigma_2}= 1 \cdot 2^2 + 1 \cdot 2^1 + 2 \cdot 2^0 = 8</math>.

Mithilfe eines Haskell-Zeileninterpreters lässt sich Letzteres schnell überprüfen:

<syntaxhighlight lang="haskell"> strings chars = [] : [ string ++ [char] | string <- strings chars, char <- chars ]

zip [0..16] (strings "12") </syntaxhighlight>

[(0,""),(1,"1"),(2,"2"),(3,"11"),(4,"12"),(5,"21"),(6,"22"),(7,"111"),(8,"112"),(9,"121"),(10,"122"),(11,"211"),(12,"212"),(13,"221"),(14,"222"),(15,"1111"),(16,"1112")]

Deutlich wird dabei, dass unser herrschendes Stellenwertsystem angesichts der zu überspringenden führenden Nullen keine Standardnummerierung im Sinne obiger Definition ergibt:

<syntaxhighlight lang="haskell"> zip [0..12] (strings "0123456789") </syntaxhighlight>

[(0,""),(1,"0"),(2,"1"),(3,"2"),(4,"3"),(5,"4"),(6,"5"),(7,"6"),(8,"7"),(9,"8"),(10,"9"),(11,"00"),(12,"01")]

<syntaxhighlight lang="haskell"> zip [0..12] (strings "1234567890") </syntaxhighlight>

[(0,""),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"0"),(11,"11"),(12,"12")]

<syntaxhighlight lang="haskell"> drop 99 $ zip [0..121] (strings "123456789X") </syntaxhighlight>

[(99,"99"),(100,"9X"),(101,"X1"),(102,"X2"),(103,"X3"),(104,"X4"),(105,"X5"),(106,"X6"),(107,"X7"),(108,"X8"),(109,"X9"),(110,"XX"),(111,"111"),(112,"112"),(113,"113"),(114,"114"),(115,"115"),(116,"116"),(117,"117"),(118,"118"),(119,"119"),(120,"11X"),(121,"121")]

<syntaxhighlight lang="haskell"> drop 90 $ zip [0..100] (strings "123456789") </syntaxhighlight>

[(90,"99"),(91,"111"),(92,"112"),(93,"113"),(94,"114"),(95,"115"),(96,"116"),(97,"117"),(98,"118"),(99,"119"),(100,"121")]

Standartnummerierung bei der Indizierung mit Buchstaben

Eine bekannte Anwendung der Standardnummerierung ergibt sich, wenn man als Alphabet die Großbuchstaben des Lateinischen Alphabet verwendet, d. h. <math>\Sigma = \{\mathrm{A},\mathrm{B},\mathrm{C},\ldots,\mathrm{Z}\}</math>.

Die Elemente der Menge der nicht leeren Zeichenketten <math>\Sigma^+</math> lassen sich nun systematisch auflisten:

<math>\Sigma^+=\{\mathrm{A}, \mathrm{B}, \ldots, \mathrm{Y}, \mathrm{Z}, \mathrm{AA}, \mathrm{AB}, \ldots, \mathrm{AY}, \mathrm{AZ}, \mathrm{BA}, \mathrm{BB}, \ldots, \mathrm{ZY}, \mathrm{ZZ}, \mathrm{AAA}, \mathrm{AAB}, \ldots\}</math>

Diese Auflistung wird in vielen Tabellenkalkulationsprogrammen zur Bennenung der Spalten verwendet.

In langen Aufzählung, die nach dem Schema a) b) c) ... durchindiziert sind, findet eine Abwandlung dieses Verfahrens gelegentlich ebenfalls Anwendung, falls mehr als 26 Items indiziert werden müssen, dann folgt auf z) das Item aa).

Auch Varianten mit einer kleinerne Menge an Buchstaben sind gebräuchlich, beispielsweise für die Benennung veränderlicher Sterne.