Cantor's Enumerations (2)

; It is possible to enumerate not only pairs of the natural numbers, ; but triplets as well. For a first step, I'll combine functions ; cantors-row and cantors column into one ; ;                  cantors-enumeration-2:N->N×N, ; ; and I'll also define inverse function ; ;               cantors-enumeration-2-inverse:N×N->N ; ; (If you want to "run" these examples, you might need to concatenate ; text of this post to text of previous post. Or, you can just read ; it as it is.) (define cantors-enumeration-2         (lambda(n)(list (cantors-row n) (cantors-column n)))) (define cantors-enumeration-2-inverse         (lambda(r c)(cantors-number r c)))          ; Now, cantor enumeration of triplets can be defined as   ; ;                cantors-enumeration-3: N-> N x N x N (define cantors-enumeration-3         (lambda(n)(append (list (cantors-row n))                           (cantors-enumeration-2 (cantors-column n))))) ; ; Is it bijection? Yes, it is - for completeness, here is the proof, ; but I advice you to skip through that, since it is very dry and ; "straight-forward." ; ; [1] Is it injection? It is, because, for every n1 and n2, ;     it is either ; ;    (1.1) (cantors-row n1) is different than (cantors-row n2), or ;    (1.2) (cantors-column n1) is different than (cantors-column n2) ; ;    if (1.1) then by definition (cantors-enumeration-3 n1) is different ;             than (cantors-enumeration-3 n2). ;    if (1.2) then (cantors-enumeration-2 (cantors-column n1)) is ;             different than (cantors-enumeration-2 (cantors-column n2)) ;             because cantors-enumeration-2 is bijection, and then ;             (cantors-enumeration-3 n1) is different than ;             (cantors-enumeration-3 n2). ; ; [2] Is it surjection? First, there is m such that ;     (cantors-enumeration-2 m)=(y z). Also, there is n such that ;     (cantros-enumeration-2 n)=(x (cantors-column m)). So, yes, ;     it is surjection as well. ; ;  We can also define inverse enumeration: (define cantors-enumeration-3-inverse         (lambda(x y z)(let((m (cantors-enumeration-2-inverse y z)))                           (cantors-enumeration-2-inverse x m)))) ; lets test it: (println "\ncantors-enumeration-3 and cantors-enumeration-3-inverse test:\n") (for(i1 1 8)    (letn((i2 (cantors-enumeration-3 i1))          (i3 (apply cantors-enumeration-3-inverse i2)))       (println (format "%2d" i1) " -> " i2 " => " (format "%2d" i3)))) ;  1 -> (1 1 1) =>  1 ;  2 -> (1 1 2) =>  2 ;  3 -> (2 1 1) =>  3 ;  4 -> (1 2 1) =>  4 ;  5 -> (2 1 2) =>  5 ;  6 -> (3 1 1) =>  6 ;  7 -> (1 1 3) =>  7 ;  8 -> (2 2 1) =>  8 (println) (for(i 1 2)   (for(j 1 2)      (for(k 1 2)         (letn((i1 (list i j k))               (i2 (cantors-enumeration-3-inverse i j k))               (i3 (cantors-enumeration-3 i2)))         (println i1 " -> " (format "%2d" i2) " => " i3))))) ; (1 1 1) ->  1 => (1 1 1) ; (1 1 2) ->  2 => (1 1 2) ; (1 2 1) ->  4 => (1 2 1) ; (1 2 2) -> 11 => (1 2 2) ; (2 1 1) ->  3 => (2 1 1) ; (2 1 2) ->  5 => (2 1 2) ; (2 2 1) ->  8 => (2 2 1) ; (2 2 2) -> 17 => (2 2 2) ; By inductions, enumeration can be defined for p-tuples, where ; p is any natural number. Perhaps p=1 is unnecessary case, but I ; defined it, however, for sake of completeness. (define (cantors-enumeration p n)         (cond ((= p 1) (list n))               ((> p 1) (cons (cantors-row n)                              (cantors-enumeration (- p 1) (cantors-column n)))))) (define (cantors-enumeration-inverse)         ; p is not needed since it can be calculated from the         ; number of arguments         (letn((arguments (args))              (p (length arguments)))                     (cond ((= p 1) (first arguments))                   ((> p 1) (apply cantors-number                                   (cons (first arguments)                                         (apply cantors-enumeration-inverse                                                (rest arguments))))))))                                                ; Test again (println "\ncantors-enumeration and cantors-enumeration-inverse test:\n") (for(i1 1 16)     (letn((i2 (cantors-enumeration 4 i1))           (i3 (apply cantors-enumeration-inverse i2)))       (println (format "%2d" i1) " -> " i2 " => " (format "%2d" i3)))) ;  1 -> (1 1 1) =>  1 ;  2 -> (1 1 2) =>  2 ;  3 -> (2 1 1) =>  3 ;  4 -> (1 2 1) =>  4 ;  5 -> (2 1 2) =>  5 ;  6 -> (3 1 1) =>  6 ;  7 -> (1 1 3) =>  7 ;  8 -> (2 2 1) =>  8 ;  9 -> (3 1 2) =>  9 ; 10 -> (4 1 1) => 10 ; 11 -> (1 2 2) => 11 ; 12 -> (2 1 3) => 12 ; 13 -> (3 2 1) => 13 ; 14 -> (4 1 2) => 14 ; 15 -> (5 1 1) => 15 ; 16 -> (1 3 1) => 16 (println) (for(i 1 2)   (for(j 1 2)     (for(k 1 2)        (for(l 1 2)           (letn((i1 (list i j k l))                 (i2 (cantors-enumeration-inverse i j k l))                 (i3 (cantors-enumeration 4 i2)))             (println i1 " -> " (format "%3d" i2) " => " i3)))))) ; (1 1 1 1) ->   1 => (1 1 1 1) ; (1 1 1 2) ->   2 => (1 1 1 2) ; (1 1 2 1) ->   7 => (1 1 2 1) ; (1 1 2 2) ->  56 => (1 1 2 2) ; (1 2 1 1) ->   4 => (1 2 1 1) ; (1 2 1 2) ->  11 => (1 2 1 2) ; (1 2 2 1) ->  29 => (1 2 2 1) ; (1 2 2 2) -> 137 => (1 2 2 2) ; (2 1 1 1) ->   3 => (2 1 1 1) ; (2 1 1 2) ->   5 => (2 1 1 2) ; (2 1 2 1) ->  12 => (2 1 2 1) ; (2 1 2 2) ->  68 => (2 1 2 2) ; (2 2 1 1) ->   8 => (2 2 1 1) ; (2 2 1 2) ->  17 => (2 2 1 2) ; (2 2 2 1) ->  38 => (2 2 2 1) ; (2 2 2 2) -> 155 => (2 2 2 2) ; Everything works. (exit)