Paringsfunktioner

Paringsfunktioner är matematiska funktioner som ger en bijektiv avbildning från mängden av par av naturliga tal till de naturliga talen. Formellt är en paringsfunktion π: N × N → N en bijektion, så att varje par (a, b) får ett unikt värde z = π(a, b) och varje z har exakt ett motsvarande par. Inverse funktioner återför först- och andrakomponenten.

Ett klassiskt exempel är Cantor-paringsfunktionen: π(a, b) = (a + b)(a + b + 1)/2 + b. Den är enkel att beräkna och inversionen kan göras genom att lösa för triangulära tal. Den används ofta i teoretiska sammanhang där två naturliga tal behöver kodas som ett enda tal utan förlust.

Ett annat vanligt alternativ är Szudziks paringsfunktion: π(a, b) = om a ≥ b då a^2 + a + b else b^2 + a. Den är ofta effektivare i praktiken och ger ofta kortare representationer än Cantor’s funktion.

Paringsfunktioner är totala, beräkningsbara och har inverser, vilket gör att de kan koda två tal till ett heltal i algoritmer, Gödel-numbering, seriellisering av datastrukturer och i teoretiska konstruktioner där flera tal behöver representeras som ett enda tal.

Generellt kan man utvidga till n-äre paringsfunktioner för tuppler och använda olika ordningar för inversioner, vilket gör att man kan koda längre sekvenser som ett enda tal. Se även Gödelnummer och sekvenser.