Standardnummerierung

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

${\alpha }_{\sigma }^{{\sigma }_{i_1}\dots {\sigma }_{i_L}}=\sum _{p=1}^L{i}_p{m}^{L-p}$

Beispiel

Sei $\mathrm{\Sigma }=\{1,2\}$ mit $(1,2)=({\sigma }_1,{\sigma }_2)$.

Die Elemente der Menge ${\mathrm{\Sigma }}^{*}$ lassen sich systematisch auflisten:

${\mathrm{\Sigma }}^{*}=\{ϵ,1,2,11,12,21,22,111,112,121,122,211,212,221,222,\dots \}$

Als i-tes Wort in der Liste erscheint stets ${\nu }_{\sigma }^i$.

${\nu }_{\mathrm{\Sigma }}^8=112$ entspricht ${\alpha }_{\sigma }^{112}={\alpha }_{\sigma }^{{\sigma }_1{\sigma }_1{\sigma }_2}=1\cdot 2^2+1\cdot 2^1+2\cdot 2^0=8$.

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

strings chars = [] : [ string ++ [char] | string <- strings chars, char <- chars ]

zip [0..16] (strings "12")

[(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:

zip [0..12] (strings "0123456789")

[(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")]

zip [0..12] (strings "1234567890")

[(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")]

drop 99 $ zip [0..121] (strings "123456789X")

[(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")]

drop 90 $ zip [0..100] (strings "123456789")

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