Re: Aufgabe::Cantornummerierung

["Udo und Susanne Krause" <su.krause@XXXXXXX.ch>]

Hallo Jens-Peer,

> also Udo hat, AFAIK,  vorwärts  und  rückwärts  vertauscht, in der  
> Informatik ist es auch so, dass
> man dem Paar {x,y} eine einzigen Index zuordnen will was mit
>
> Cantor[{x_Integer, y_Integer}] := (x + y)*(x + y + 1)/2 + y
>
> passiert (entspricht dem gewünschten cantorInverseD[] von Udo).
> Die umgekehrte Variante erhält man mit
>
> InverseCantor[z_Integer] :=
>  InverseCantor[z] =
>   With[{j = Floor[Sqrt[2*z + 1/4] - 1/2]},
>    Block[{y}, y = z - j*(j + 1)/2; {j - y, y}]]

Dieser Code durchläuft die Diagonalen stets in der gleichen Richtung, das  
ist bei Cantors Diagonalverfahren jedoch nicht der Fall (vgl.  
http://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument), die  
aufeinanderfolgenden Diagonalen werden in gegenlaeufiger Richtung  
durchlaufen (siehe Bildchen bei der Aufgabe), und das kann man mit

Remove[cantorD, cantorInverseD]
cantorD[n_Integer?NonNegative, dir_: - 1] :=
 Block[{q = Floor[(Sqrt[1  + 8  n ] + 1)/2], o = n - q  (q  + 1)/2},
   If[Xor[dir == -1, EvenQ[q]], {q + o, -(o + 1)},  {-(o + 1), q + o}]
   ] /; (dir == -1 || dir == 1)

cantorInverseD[{i_Integer?NonNegative, j_Integer?NonNegative},
  dir_: - 1] := (i + j) (i + j + 1)/2 +
   If[Xor[dir == -1, EvenQ[i + j]], j,  i] /; (dir == -1 || dir == 1)

für beide Varianten (dir = -1 oder 1) tun, ohne Reverse[] zu verwenden.

Gruss
Udo.

> wobei erstmal geklärt werden sollte wie lang die Zeile eine Einzeilers  
> sein darf, denn
>
> InverseCantor[z_Integer] :=
>   With[{j = Floor[Sqrt[2*z + 1/4] - 1/2]}, {j*(j + 3)/2 - z,  z - j*(j +  
> 1)/2}]
>
> ist zwar kürzer aber nur teilweise schöner. Natürlich gibt's das schon  
> auf MathWorld
> http://mathworld.wolfram.com/PairingFunction.html
>
> Und ein Bild gibt's mit
>
> grid = Flatten[Table[{i, j}, {i, 0, 5}, {j, 0, 5}], 1];
> Graphics[{
>   {Point[#], Text[Cantor[#], #, {-1, -1}]} & /@ grid,
>   Arrow[{#[[1, 1]], #[[2, 1]]}, 0.1] & /@  Select[Partition[
>      Sort[{#, Cantor[#]} & /@ grid, Last[#1] < Last[#2] &], 2,
>      1], #[[1, 2]] + 1 === #[[2, 2]] &]
>   }, Frame -> True, PlotRangePadding -> 0.5]
>
>
> Gruss
>   Jens