### Cantor's Enumerations (1)

 ; George Cantor discovered that set of all pairs of the natural ; numbers is countable; i.e, there is bijective map ; ;                     N -> N × N ; ; where N is set of all natural numbers. This is the simplest ; bijection of that kind: ; ; Each natural number, n is mapped to some pair of natural numbers, ; (r, c). That pair is on diagonale d. Inverse mapping is defined ; as well; for every pair of natural numbers, (r, c) there is a ; natural number n such that n is mapped to (r, c). However, if we ; want to write programs that use Cantor's enumeration, then we need ; explicit formulas. ; ; Let's say that n is given. First, we can calculate d, the diagonale ; on which n is placed. From picture ; ;           n <= 1 + 2 + ... + d = d * (d + 1) / 2 ;                          ; i.e. we search for minimal natural number d such ; ;                d^2 + d - 2n >= 0 ;                 ;                d = ceil ( - 1 + sqrt (1 + 8*n) / 2) ;                 ; When we know d, then it is easy to calculate ; ;                r = n - d * (d - 1) / 2 ;                 ;                c = d - r + 1 ;                 ; Inversly, if r and c are given, then d can be calculated as ; ;                d = c + r - 1 ;                 ; and            n = d * (d - 1) /2 + r ;             ; I'll define Newlisp functions, using longer names; ; ; First, lets define functions that calculate d, r and c on the ; base of n. I'll give longer names to these functions: ; cantors-diagonal1, cantors-row and cantors-column respectively. (setf cantors-diagonal1   (lambda(n)(ceil (div (add (- 1)                             (sqrt (add 1 (mul 8 n))))                         2)))) (setf cantors-row    (lambda (n)       (let ((cd (cantors-diagonal1 n)))            (- n (/ (* cd                       (- cd 1))                    2)))))                                (setf cantors-column (lambda (n) (+ (cantors-diagonal1 n)                                     (- (cantors-row n))                                     1)))                                      ; Second, lets define functions that calcualte d and n on the base ; of r and c. I'll give longer names to these functions: ; cantors-diagonal2, and cantors-number. (setf cantors-diagonal2 (lambda(r c)(+ c r (- 1))))        (setf cantors-number       (lambda(r c)          (let ((cd (cantors-diagonal2 r c)))                (+ (/ (* cd (- cd 1)) 2) r))))                 ; Lets try two simple tests: (for(n 1 10)   (println (format "%2d" n) " -> " (list (cantors-row n) (cantors-column n))              ", diagonal="  (cantors-diagonal1 n))) (println) (for(r 1 3)   (for(c 1 3)      (print "(" r "," c ") => "             (format "n=%2d, " (cantors-number r c))             (format "d=%1d;  " (cantors-diagonal2 r c))))   (println)) (exit) ; Everything works. ; ; ;  1 -> (1 1), diagonal=1 ;  2 -> (1 2), diagonal=2 ;  3 -> (2 1), diagonal=2 ;  4 -> (1 3), diagonal=3 ;  5 -> (2 2), diagonal=3 ;  6 -> (3 1), diagonal=3 ;  7 -> (1 4), diagonal=4 ;  8 -> (2 3), diagonal=4 ;  9 -> (3 2), diagonal=4 ; 10 -> (4 1), diagonal=4 ; ; (1,1) => n= 1, d=1;  (1,2) => n= 2, d=2;  (1,3) => n= 4, d=3; ; (2,1) => n= 3, d=2;  (2,2) => n= 5, d=3;  (2,3) => n= 8, d=4; ; (3,1) => n= 6, d=3;  (3,2) => n= 9, d=4;  (3,3) => n=13, d=5; ; ; Cantor's row and Cantor's column remind on well known operators ; "div" and "mod", don't they?

--