Discussion:
Invertierung einer Tripelungsfunktion?
(zu alt für eine Antwort)
Stefan Ram
2018-03-10 21:49:32 UTC
Permalink
Es gibt eine Cantor-Paarungsfunktion ("Cantor['s] pairing
function") g, die jedem Paar natürlicher Zahlen eineindeutig
eine natürliche Zahl zuordnet.

Laut Literatur ist g(x,y) = (x+y)*(x+y+1)/2 + y.

Laut Literatur ist das folgende eine Invertierung,
die aus der Zahl g wieder ein Paar (x,y) macht
(in der Programmiersprache C):

int pair( double const g )
{ double const S = 8*g+1;
double const Q = sqrt(S);
double const P = Q - 1;
double const D = P/2;
double const F = floor(D);
long const w = ( long )F;
long const t = (w*w + w) / 2;
long const y = z - t;
long const x = w - y;
printf( "%ld %ld\n", x, y ); }

In der Literatur finde ich, daß man auch jedem Tripel (x,y,z)
eineindeutig wieder eine Zahl zuordnen kann. Nämlich G=g(g(x,y),z).

Wie kann ich jetzt aus einer Zahl G wieder die drei
Komponenten x, y und z gewinnen? Also G "invertieren",
so wie pair g invertiert.

PS:

Wie man hier sieht, kann ich mit "pair" alle Paare
generieren:

#include <stdio.h>
#include <math.h>

int pair( double const z )
{ double const S = 8*z+1;
double const Q = sqrt(S);
double const P = Q - 1;
double const D = P/2;
double const F = floor(D);
long const w = ( long )F;
long const t = (w*w + w) / 2;
long const y = z - t;
long const x = w - y;
printf( "%g:( %ld, %ld )\n", z, x, y ); }

int main( void )
{ for( int i = 0; i < 10; ++i )pair( i ); }

Ausgabe:

0:( 0, 0 )
1:( 1, 0 )
2:( 0, 1 )
3:( 2, 0 )
4:( 1, 1 )
5:( 0, 2 )
6:( 3, 0 )
7:( 2, 1 )
8:( 1, 2 )
9:( 0, 3 )

... und so weiter.

Nun möchte ich auf analoge Weise alle /Tripel/ generieren.
Dazu muß ich jetzt G "invertieren". Was ich leider bisher
nicht in der Literatur fand. Naiv erwarte ich, daß ich
dazu zwei Anwendung von "pair" kombinieren muß, bin mir
aber nicht sicher.
Valentin Schmidt
2018-03-11 02:25:17 UTC
Permalink
Post by Stefan Ram
Nun möchte ich auf analoge Weise alle /Tripel/ generieren.
Dazu muß ich jetzt G "invertieren". Was ich leider bisher
nicht in der Literatur fand. Naiv erwarte ich, daß ich
dazu zwei Anwendung von "pair" kombinieren muß, bin mir
aber nicht sicher.
Vergiss mal vorübergehend den Code, und denke nur logisch nach:

wenn du eine Funktion hast, die einem Zahlenpaar (x,y) eindeutig eine
Zahl c zuordnen kann, kannst du natürlich auch einem Zahlen-Tripel
(x,y,z) eindeutig eine Zahl zuordnen, indem du zuerst in einem
Zwischenschritt (x,y) über obige Funktion eine Zahl cn zuordnest, und
danach dann eine Zahl dem neuen Paar (cn,z), und damit hast du dein
Ergebnis. Das ist eigentlich relativ banal. Und natürlich kannst du auf
die gleiche Weise dann auch beliebige n-Tupel als Zahlen kodieren.

Da ich C-Code für eher ungeeignet für schnelles erfassen eines
Algorithmus halte, hier stattdessen in einer Script-Sprache mit
dynamischer Typisierung (Lua, alle "local" weggelassen):
(Warnung: ungetesteter Code, geht ja nur ums Prinzip)

----------------------------------------
-- Berechnet x, y für Cantorsche Paar-Zahl c, die Paar (x,y) kodiert
----------------------------------------
function computePair (c)
j = floor(sqrt(0.25 + 2*c) - 0.5)
x = j - (z - j*(j+1)/2)
y = c - j*(j+1)/2
return x, y
end

----------------------------------------
-- Berechnet x, y, z für Cantorsche Tripel-Zahl c,
-- die Tripel (x,y,z) kodiert
----------------------------------------
function computeTriple (c)
cn, z = computePair(c)
x, y = computePair(cn)
return x, y, z
end

Valentin
Valentin Schmidt
2018-03-11 14:22:15 UTC
Permalink
Post by Valentin Schmidt
Da ich C-Code für eher ungeeignet für schnelles erfassen eines
Algorithmus halte, hier stattdessen in einer Script-Sprache mit
(Warnung: ungetesteter Code, geht ja nur ums Prinzip)
----------------------------------------
-- Berechnet x, y für Cantorsche Paar-Zahl c, die Paar (x,y) kodiert
----------------------------------------
function computePair (c)
j = floor(sqrt(0.25 + 2*c) - 0.5)
x = j - (z - j*(j+1)/2)
y = c - j*(j+1)/2
return x, y
end
Wie das mit ungestetem Code so ist, funktioniert er bekanntlich nie ;)
Aus einem "z" musste noch ein "c" gemacht werden, und "floor" muss als
"math.floor" geschrieben werden.

Hier nochmal korrekt, diesmal getestet (lua 5.1.4):

----------------------------------------
-- Berechnet x, y für Cantorsche Paar-Zahl c, die Paar (x,y) kodiert
----------------------------------------
function computePair (c)
local j = math.floor(sqrt(0.25 + 2*c) - 0.5)
local x = j - (c - j*(j+1)/2)
local y = c - j*(j+1)/2
return x, y
end


Und bei der Gelegenheit auch gleich Code für Kodierung und Dekodierung
beliebiger n-Tupel:

----------------------------------------
-- Berechnet Cantorsche Paar-Zahl
----------------------------------------
function cantor (x,y)
return (x+y)*(x+y+1)/2 + y;
end

----------------------------------------
-- Berechnet Cantorsche Tupel-Zahl für ein n-Tupel
----------------------------------------
function cantorN (...)
local c = arg[1]
for i = 2,#arg,1 do c = cantor(c,arg[i]) end
return c
end

----------------------------------------
-- Berechnet n-Tupel n1, n2, ..., nn für Cantorsche Tupel-Zahl c
----------------------------------------
function computeTuple (c, n)
local res = {}
for i = n,3,-1 do c, res[i] = computePair(c) end
res[1], res[2] = computePair(c)
return unpack(res)
end

Test:
=====

c = cantorN(4, 7, 5, 9)
print(c)
-- 4791069

print(computeTuple(c, 4))
-- 4 7 5 9
Detlef Müller
2018-03-11 17:27:31 UTC
Permalink
Post by Stefan Ram
Es gibt eine Cantor-Paarungsfunktion ("Cantor['s] pairing
function") g, die jedem Paar natürlicher Zahlen eineindeutig
eine natürliche Zahl zuordnet.
Laut Literatur ist g(x,y) = (x+y)*(x+y+1)/2 + y.
Laut Literatur ist das folgende eine Invertierung,
die aus der Zahl g wieder ein Paar (x,y) macht
int pair( double const g )
[...]
Post by Stefan Ram
In der Literatur finde ich, daß man auch jedem Tripel (x,y,z)
eineindeutig wieder eine Zahl zuordnen kann. Nämlich G=g(g(x,y),z).
Wie kann ich jetzt aus einer Zahl G wieder die drei
Komponenten x, y und z gewinnen? Also G "invertieren",
so wie pair g invertiert.
Was spricht dagegen, aus G erst g und z auszupacken und aus
g dann x und y, also:

(g,z) := pair(G)
(x,y) := pair(g) ?

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Loading...