; 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? |
--
No comments:
Post a Comment