Die Cantorsche Paarungsfunktion, manchmal auch Nummerierungsfunktion genannt, ist eine unter anderem in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert.

Mit ihr kann man ein beliebiges Paar ${\displaystyle (x,y)}$ natürlicher Zahlen durch eine einzige natürliche Zahl ${\displaystyle n}$ darstellen. Man nummeriert damit alle Zahlenpaare. Diese Nummerierung ist sogar eindeutig umkehrbar. Das heißt, man kann aus der Zahl ${\displaystyle n}$ das ursprüngliche Zahlenpaar ${\displaystyle (x,y)}$ wieder ermitteln. Mathematisch gesprochen heißt das: Die Cantorsche Paarungsfunktion ist eine bijektive totale Funktion ${\displaystyle \pi \colon \mathbb {N} ^{2}\to \mathbb {N} }$.

Die Idee der diagonalen Abzählung der Menge aller Paare natürlicher Zahlen geht auf Georg Cantor zurück. Die Verallgemeinerung der Cantorschen Paarungsfunktion von Paaren auf Tupel wird als Cantorsche Tupelfunktion bezeichnet.

Motivation

In der theoretischen Informatik wird die Cantorsche Paarungsfunktion bzw. Tupelfunktion benutzt, um Funktionen, die mehr als einen Parameter haben, auf Funktionen zurückzuführen, die nur genau einen Parameter haben, was viele Beweise deutlich erleichtert.

Die Zurückführung eines Problems auf ein (eventuell einfacheres) bereits bekanntes Problem ist eine bewährte Beweistechnik, die man als Reduktion bezeichnet.

Mit der Cantorschen Paarungsfunktion bzw. Tupelfunktion lässt sich die Berechenbarkeit von ${\displaystyle k}$-stelligen Zahlenfunktionen auf die Berechenbarkeit von einstelligen Zahlenfunktionen reduzieren. Das heißt, man kann sich bei der Untersuchung der Berechenbarkeit von Zahlenfunktionen auf die Untersuchung von Einstelligen beschränken und weiß, dass die gewonnenen Ergebnisse für alle (also auch für die mehrstelligen) Zahlenfunktionen gelten.

Grundsätzliches

Es ist vielleicht nicht unmittelbar einsichtig, dass es möglich ist, alle beliebigen Kombinationen von zwei Zahlen durch eine Zahl zu kodieren: Die Menge aller Zahlenpaare ${\displaystyle \mathbb {N} ^{2}=\mathbb {N} \times \mathbb {N} }$ scheint viel größer zu sein als die Menge aller Zahlen ${\displaystyle \mathbb {N} }$. Die Cantorsche Paarungsfunktion zeigt jedoch, dass beide Mengen gleich groß sind, denn sie stellt eine 1:1-Beziehung her. Sie ist eine Bijektion.

Eine Menge, die man bijektiv auf die natürlichen Zahlen abbilden kann, nennt man abzählbar unendlich; insbesondere haben die natürlichen Zahlen selbst diese Eigenschaft. Die Cantorsche Paarungsfunktion zeigt dann, dass auch die Menge der Paare natürlicher Zahlen abzählbar unendlich ist.

Definition

Die Cantorsche Paarungsfunktion definiert man als

${\displaystyle \pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$

${\displaystyle (x,y)\mapsto \pi (x,y):=y+\sum _{i=0}^{x+y}i=y+{\frac {1}{2}}(x+y)(x+y+1)}$,

wobei man die natürlichen Zahlen bei 0 beginnen lässt. (Siehe z. B. DIN-Norm 5473)

Kurzschreibweise:

${\displaystyle \langle x,y\rangle =\pi (x,y)=n}$

${\displaystyle n}$ kodiert das Paar ${\displaystyle (x,y)}$

Hier ist eine Skizze der Diagonal-Abzählung:

Auf den Achsen sind die beiden Werte aufgetragen, wie in einer Entfernungstabelle schlägt man den Wert der Cantorschen Paarungsfunktion im Schnittpunkt nach, zum Beispiel ${\displaystyle \langle 1,2\rangle =8}$.

Die Nummerierung ist denkbar einfach: Man zählt diagonal mit Null beginnend die Paare ab: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2) usw.

Man kann das obige Bildungsgesetz direkt ablesen, wenn man sich die Summation jeweils über eine Spalte verdeutlicht.

Erweiterung auf k-Tupel

Durch mehrfache Anwendung lassen sich auch ${\displaystyle k}$-Tupel eindeutig nummerieren. Man definiert induktiv für ${\displaystyle k=1,2,3,\dotsc }$ die Funktionen

${\displaystyle \pi ^{(k)}\colon \mathbb {N} ^{k}\to \mathbb {N} }$

mit Hilfe der Paarungsfunktion ${\displaystyle \pi }$ durch:

${\displaystyle \pi ^{(1)}(x)=x}$

und

${\displaystyle \pi ^{(k+1)}(x_{1},\dotsc ,x_{k+1})=\pi (\pi ^{(k)}(x_{1},\dotsc ,x_{k}),x_{k+1})}$

Die Funktionen ${\displaystyle \pi ^{(k)}}$ bezeichnet man als Cantorsche Tupelfunktionen.

Kurzschreibweise:

${\displaystyle \langle x_{1},x_{2},\dotsc ,x_{k}\rangle$ :=\pi ^{(k)}(x_{1},x_{2},\dotsc ,x_{k})}

Umkehrfunktion

Die Cantorsche Paarungsfunktion besitzt als Umkehrfunktion die Dreieckswurzel. Die Umkehrung ist eindeutig und berechenbar. Letzteres ist für die Anwendung in der theoretischen Informatik wichtig, da die Berechenbarkeit der Funktion und der Umkehrfunktion Bedingung ist, um ohne Probleme alle berechenbaren Funktionen durch einstellige Funktionen darzustellen.

Umkehrbar heißt, man kann aus einer Zahl ${\displaystyle n}$ auf die beiden Zahlen ${\displaystyle x}$ und ${\displaystyle y}$ schließen, für die ${\displaystyle \pi (x,y)=n}$ gilt. Die Umkehrfunktion setzt sich aus zwei Hilfsfunktionen ${\displaystyle f}$ und ${\displaystyle q}$ zusammen:

j 00 0    1    2    3    4    5    6
f(j) 0    1    3    6   10   15   21

Computerimplementierungen

  public class Cantor {
    public static long compute(long x, long y) {
      return (x+y)*(x+y+1)/2 + y;
    }
    public static long computeX(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return j - (z - j*(j+1)/2);
    }
    public static long computeY(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return z - j*(j+1)/2;
    }
  }

from math import isqrt

def cantor(x, y):
    return (x + y) * (x + y + 1) // 2 +  y

def invCantor(z):
    j = (isqrt(8 * z + 1) - 1) // 2
    x = j - (z - j * (j + 1) // 2)
    y = z - j * (j + 1) // 2
    return (x, y)

 procedure CantorPair(I : Integer; Var X,Y : Integer);
 { Gibt das i-te Paar (X,Y) in Diagonalabzaehlung zurueck }
 var
    J : Integer;

    function F(Z : Integer) : Integer;
    begin
       F := (Z * (Z + 1)) div 2
    end;

    function Q(Z : Integer) : Integer;
    var
       V : Integer;
    begin
       V := 0;
       while F(V) <= Z do
          V := V + 1;
       Q := V - 1
    end;

 begin
    J := Q(I);
    Y := I - F(J);
    X := J - Y;
 end;

Berechenbarkeit

Die Cantorsche Paarungsfunktion ist eine totale, bijektive, berechenbare (sogar primitiv-rekursive) Funktion, daher ist auch ihre Umkehrung berechenbar.

R4 = R1 + R2
R5 = R4 + 1
R4 = R4 * R5
R4 = R4 / 2
R0 = R4 + R2

Herkunft

Die Idee stammt aus der Mengenlehre von Georg Cantor. Er hatte die Idee, die Größe einer Menge (Mächtigkeit, Kardinalität) mit der Größe einer anderen Menge zu vergleichen, indem man versucht, eine 1:1-Abbildung (Bijektion) dieser Menge mit der anderen Menge zu finden. Jedem Element der ersten Menge soll genau ein Element der zweiten Menge zugeordnet werden und umgekehrt. Das erscheint kompliziert, findet aber seine Berechtigung, wenn es um Mengen mit unendlich vielen Elementen geht. Siehe auch Galileis Paradoxon.

Mit einer Diagonal-Abzählung (wie oben angedeutet) zeigt man leicht, dass bei einer abzählbaren Menge ${\displaystyle M}$ das kartesische Produkt ${\displaystyle M\times M=M^{2}=\{(a,b)\mid a,b\in M\}}$ gleichmächtig ist zu ${\displaystyle M}$, was vielleicht gegen die Intuition spricht, da hier Tupel verschiedener Dimension auftreten.

Alternativen

Für zwei benachbarte Punkte ${\displaystyle (x,y)}$ und ${\displaystyle (x',y')}$ auf der Trajektorie der Umkehrfunktion kann ${\displaystyle \max(|x-x'|,|y-y'|)}$ beliebig groß werden, was bei der Anwendung der Abzählung unerwünscht sein kann. Daher betrachtet man auch eine Variante der Cantorschen Abzählung, bei der stets ${\displaystyle \max(|x-x'|,|y-y'|)=1}$ gilt und die in diesem Sinn stetig ist. Diese Form wird die boustrophedonische Cantor-Abzählung genannt, da hier der Pfad nicht von der ${\displaystyle y}$-Achse zur ${\displaystyle x}$-Achse springt (wie in der Skizze oben dargestellt), sondern an den Achsen wendet. Sie ist auf OEIS als A319571 beschrieben.

Es gibt viele andere Möglichkeiten, Paare natürlicher Zahlen bijektiv durch eine natürliche Zahl zu kodieren, z. B. kann man mit der Formel ${\displaystyle \max(r,c)^{2}+\max(r,c)+(-1)^{1+\max(r,c){\text{ mod }}2}\cdot (r-c)}$ spiralförmig abzählen:

Auch die einfache Formel ${\displaystyle 2^{x}\cdot (2y+1)}$ liefert eine Bijektion zwischen ${\displaystyle {\mathbb {N} }\times {\mathbb {N} }}$ und ${\displaystyle {\mathbb {N} }\setminus \{0\}}$:

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 1   3   5   7   .
 1 | 2   6  10  14   .
 2 | 4  12  20  28   .         ${\displaystyle z=2^{x}\cdot (2y+1)}$
 3 | 8  24  40  56   .
 4 | .   .   .   .   .
   |
 x v

Beweis der Umkehrbarkeit: ${\displaystyle x}$ ist die größte natürliche Zahl so, dass ${\displaystyle 2^{x}}$ ein Teiler von ${\displaystyle z}$ ist, also die Anzahl der Faktoren ${\displaystyle 2}$ in der Primfaktorzerlegung von ${\displaystyle z}$. Sei ${\displaystyle R={\tfrac {z}{2^{x}}}}$. Dann ist ${\displaystyle y={\tfrac {R-1}{2}}}$.

Die Primfaktorzerlegung gibt eine Möglichkeit an, beliebige endliche Tupel natürlicher Zahlen durch natürliche Zahlen zu kodieren:

${\displaystyle \langle i_{1},i_{2},i_{3},i_{4},i_{5},\dotsc \rangle =2^{i_{1}}3^{i_{2}}5^{i_{3}}7^{i_{4}}11^{i_{5}}\dotsb }$

Beispiel:

${\displaystyle \langle 2,1,0,1,0,0\rangle =2^{2}3^{1}5^{0}7^{1}11^{0}13^{0}=4\cdot 3\cdot 7=84}$

Literatur

• Klaus Weihrauch: Computability. Springer, Berlin u. a. 1987, ISBN 3-540-13721-1 (EATCS monographs on theoretical computer science 9).
• Eric W. Weisstein: Pairing Function. In: MathWorld (englisch).
• Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 263 f. (Springer-Lehrbuch).
• Uwe Schöning: Theoretische Informatik – kurzgefasst. 4. Auflage. Korrigierter Nachdruck. Spektrum, Heidelberg u. a. 2003, ISBN 3-8274-1099-1, S. 111 f. (Hochschultaschenbuch).

Einzelnachweise

1. ↑ Christoph Michel: Enumerating a Grid in Spiral Order. In: cmichel.io Blog. 7. September 2016, abgerufen am 7. September 2016 (englisch).