CODEWITHSUNDEEP
arraysalgorithmmathiterator
dreeves
dreeves

Reputation: 26952

Cantor's ZigZag Function: Find the nth cell

Suppose I want to traverse a grid like in Cantor's proof of the countability of the rationals...

Cantor ZigZag

What's a function that takes an integer n and returns the row and column number for the nth cell in that traversal?

Upvotes: 2

Views: 786

Answers (2)

dreeves
dreeves

Reputation: 26952

First we need the formula for the nth triangular number, as well as the inverse of that function:

t[n_] := n*(n+1)/2
ti[x_] := Floor[(Sqrt[8*x+1]-1)/2]

Then we can define Cantor's ZigZag like so:

zig[n_] := Module[{y = n-1-t[ti[n-1]]}, 
  {ti[n-1]-y, y} + 1]

(I wrote and tested this in Mathematica but it's just arithmetic so will look about the same in any language.)

Upvotes: 1

amara
amara

Reputation: 2286

If you just want a traversal there's no need for a closed form.

You can just use a sequence:

function*(grid){var r=0, c=0
    for(;;){yield grid[r][c]; c++; r--; if (r === -1) {r = c; c = 0}}
    }

Upvotes: 3

Related Questions