Pairing Functions

Overview of functions that map ZxZ->N

by Steven Sell

HTML

<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js"></script>
<script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<script type="text/x-mathjax-config"> MathJax.Hub.Config({   tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); </script>

<div id="contents">

    <h2>
    Cantor Pairing Function
    </h2>
    
    Assigns consecutive numbers to points along diagonals in the plane.
    
    <br/><br/>
    
    $$index = {(x + y)(x + y + 1) \over 2} + y$$
    
    ( <input id="cantor_input_x" type="Number"> , <input id="cantor_input_y" type="Number"> ) = <span id="cantor_result"></span>
    
    <br/><br/>
    
    <table id="cantor_table" cellspacing="0">
        <tr id="cantor_table_head"></tr>
    </table>
    
    <br/><br/>
    
    <img src="http://i.imgur.com/jURUPLG.png" width="250px" height="250px">

    <h2>
    Szudzik Pairing Function
    </h2>
    
    Assigns consecutive numbers to points along the edges of squares.
    
    <br/><br/>
    
    $$index(x,y) = \left\{\begin{array}{ll}
    y^2 + x & : x < y\\
    x^2 + x + y & : x \ge y
    \end{array}
    \right.$$
    
    ( <input id="szudzik_input_x" type="Number"> , <input id="szudzik_input_y" type="Number"> ) = <span id="szudzik_result"></span>
    
    <br/><br/>
    
    <table id="szudzik_table" cellspacing="0">
        <tr id="szudzik_table_head"></tr>
    </table>
    
    <br/><br/>
    
    Notice the tighter packing using the Szudzik function compared to Cantor's. 
    
    <br/><br/>
    
    220 indices generated for an 11x11 region with Cantor, while Szudzik uses only 121 indices.
    
    <br/><br/>
    
    <img src="http://i.imgur.com/KQGrIE2.png" width="250px" height="250px">

    <h2>
    On Negatives
    </h2>
    
    Neither pairing function works natively with signed (negative) values.
    
    <br/><br/>
    
    The following transformations must be done in order to calculate a pair index for negative...

CSS

input {
  position: inline-block;
  width: 50px;
}

.heading {
  background-color: #222;
  color: #FFF;
  text-align: center;
  width: 50px;
}

.cell {
  background-color: #FFF;
  color: #000;
}

.dark {
  background-color: #DDD;
}

JavaScript

/**
 * Classic Cantor Pairing Function
 * Works only on non-negative numbers.
 */
function cantorPair(x, y) {
    
    return (0.5 * (x + y) * (x + y + 1)) + y;
}

/**
 * Modified Cantor Pairing that works with negative values.
 */
function cantorPairSigned(x, y) {
    const a = (x >= 0.0 ? 2.0 * x : (-2.0 * x) - 1.0);
    const b = (y >= 0.0 ? 2.0 * y : (-2.0 * y) - 1.0);
    return cantorPair(a, b);
}

/**
 * Szudzik Pairing Function.
 */
function szudzikPair(x, y) {
    return (x >= y ? (x * x) + x + y : (y * y) + x);
}

/**
 * Modified Szudzik Pairing Function that works with negative values.
 */
function szudzikPairSigned(x, y) {
    const a = (x >= 0.0 ? 2.0 * x : (-2.0 * x) - 1.0);
    const b = (y >= 0.0 ? 2.0 * y : (-2.0 * y) - 1.0);
    const c = szudzikPair(a, b) * 0.5;
    
    var result = index;
    
    if(((a >= 0.0) && (b < 0.0)) || ((a < 0.0) && (b >= 0.0))) {
        result = -c - 1;
    }
    
    return result;
}

function calculateCantor() {
    const x = Number($("#cantor_input_x").val());
    const y = Number($("#cantor_input_y").val());
    
    console.log("x = " + x + " | y = " + y);
    
    $("#cantor_result").html(cantorPair(x, y));
}

function calculateSzudzik() {
    const x = Number($("#szudzik_input_x").val());
    const y = Number($("#szudzik_input_y").val());
    
    console.log("x = " + x + " | y = " + y);
    
    $("#szudzik_result").html(szudzikPair(x, y));
}

function populate(count, pairFunc, name) {
    
    var table = $("#" + name + "_table");
    var tableHead = $("#" + name + "_table_head");
    
    if(tableHead) {
        tableHead.append("<td class='heading'>&nbsp;</td>");
        for(var i = 0; i < count; ++i) {
            tableHead.append("<td class='heading'>" + (i == 0 ? "x" : "") + i + "</td>");
        }
    }
    
    if(table) {
        var light = true;
        
        for(var x = 0; x < count; ++x) {
            table.append("<tr id='" + name + "_row_" + x + "' class='heading'><td>" + (x == 0 ? "y" :...