Module: MoreMath::CantorPairingFunction

Defined in:
lib/more_math/cantor_pairing_function.rb

Overview

Provides Cantor pairing function implementations for encoding tuples into natural numbers and decoding them back.

The Cantor pairing function is a mathematical construct that uniquely encodes pairs of natural numbers into a single natural number, and vice versa. This module implements both the forward pairing function and its inverse for arbitrary tuples of integers.

Examples:

Pairing two numbers

CantorPairingFunction.cantor_pairing(5, 3) # => 39

Pairing multiple numbers

CantorPairingFunction.cantor_pairing(1, 2, 3) # => 69

Inverse pairing

CantorPairingFunction.cantor_pairing_inv(39) # => [5, 3]

Inverse pairing for tuples

CantorPairingFunction.cantor_pairing_inv(69, 3) # => [1, 2, 3]

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.cantor_pairing(*xs) ⇒ Integer

Encodes multiple integers into a single natural number using the Cantor pairing function.

This method implements the Cantor pairing function, which provides a unique encoding of tuples of natural numbers into a single natural number. For two integers, it uses the standard Cantor pairing formula. For more than two integers, it recursively applies the pairing function to reduce the tuple to a single value.

Parameters:

  • xs (Array<Integer>) —

    An array of integers to pair

Returns:

  • (Integer) —

    A unique natural number representing the input tuple

Raises:

  • (ArgumentError) —

    When fewer than two arguments are provided



37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/more_math/cantor_pairing_function.rb', line 37

def cantor_pairing(*xs)
  if xs.size == 1 and xs.first.respond_to?(:to_ary)
    xs = xs.first.to_ary
  end
  case xs.size
  when 0, 1
    raise ArgumentError, "at least two arguments are required"
  when 2
    x, y, = *xs
    (x + y) * (x + y + 1) / 2 + y
  else
    cantor_pairing(cantor_pairing(*xs[0..1]), *xs[2..-1])
  end
end

.cantor_pairing_inv(c, n = 2) ⇒ Array<Integer>

Computes the inverse of the Cantor pairing function for a given value

This method decodes a natural number back into its original tuple representation using the inverse Cantor pairing function. It supports decoding tuples of arbitrary length by recursively applying the inverse operation.

Parameters:

  • c (Integer) —

    The natural number to decode back into a tuple

  • n (Integer) (defaults to: 2) —

    The length of the original tuple (default: 2)

Returns:

  • (Array<Integer>) —

    The decoded tuple as an array of integers

Raises:

  • (ArgumentError) —

    When n is less than 2



92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/more_math/cantor_pairing_function.rb', line 92

def cantor_pairing_inv(c, n = 2)
  raise ArgumentError, "n is required to be >= 2" unless n >= 2
  result = []
  begin
    q = CantorPairingFunction.cantor_pairing_inv_q(c)
    y = c - CantorPairingFunction.cantor_pairing_inv_f(q)
    x = q - y
    result.unshift y
    c = x
    n -= 1
  end until n <= 1
  result.unshift x
end

.cantor_pairing_inv_f(z) ⇒ Integer

Computes the cantor pairing function f(z) = z * (z + 1) / 2

This helper method calculates a partial result used in the inverse cantor pairing function to compute the triangular number sequence that helps in decoding paired values

Parameters:

  • z (Integer) —

    The input value to compute the triangular number for

Returns:

  • (Integer) —

    The computed triangular number value



60
61
62
 
# File 'lib/more_math/cantor_pairing_function.rb', line 60

def self.cantor_pairing_inv_f(z)
  z * (z + 1) / 2
end

.cantor_pairing_inv_q(z) ⇒ Integer

Computes the quotient used in the inverse Cantor pairing function

This method calculates the largest value v such that the Cantor pairing function applied to v is less than or equal to the given value z. It’s a helper method that supports the inverse pairing algorithm by determining the appropriate triangular number boundary for decoding.

Parameters:

  • z (Integer) —

    The value to compute the quotient for

Returns:

  • (Integer) —

    The computed quotient value v where cantor_pairing_inv_f(v) <= z



73
74
75
76
77
78
79
 
# File 'lib/more_math/cantor_pairing_function.rb', line 73

def self.cantor_pairing_inv_q(z)
  v = 0
  while cantor_pairing_inv_f(v) <= z
    v += 1
  end
  v - 1
end

Instance Method Details

#cantor_pairing(*xs) ⇒ Integer (private)

Encodes multiple integers into a single natural number using the Cantor pairing function.

This method implements the Cantor pairing function, which provides a unique encoding of tuples of natural numbers into a single natural number. For two integers, it uses the standard Cantor pairing formula. For more than two integers, it recursively applies the pairing function to reduce the tuple to a single value.

Parameters:

  • xs (Array<Integer>) —

    An array of integers to pair

Returns:

  • (Integer) —

    A unique natural number representing the input tuple

Raises:

  • (ArgumentError) —

    When fewer than two arguments are provided



37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/more_math/cantor_pairing_function.rb', line 37

def cantor_pairing(*xs)
  if xs.size == 1 and xs.first.respond_to?(:to_ary)
    xs = xs.first.to_ary
  end
  case xs.size
  when 0, 1
    raise ArgumentError, "at least two arguments are required"
  when 2
    x, y, = *xs
    (x + y) * (x + y + 1) / 2 + y
  else
    cantor_pairing(cantor_pairing(*xs[0..1]), *xs[2..-1])
  end
end

#cantor_pairing_inv(c, n = 2) ⇒ Array<Integer> (private)

Computes the inverse of the Cantor pairing function for a given value

This method decodes a natural number back into its original tuple representation using the inverse Cantor pairing function. It supports decoding tuples of arbitrary length by recursively applying the inverse operation.

Parameters:

  • c (Integer) —

    The natural number to decode back into a tuple

  • n (Integer) (defaults to: 2) —

    The length of the original tuple (default: 2)

Returns:

  • (Array<Integer>) —

    The decoded tuple as an array of integers

Raises:

  • (ArgumentError) —

    When n is less than 2



92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/more_math/cantor_pairing_function.rb', line 92

def cantor_pairing_inv(c, n = 2)
  raise ArgumentError, "n is required to be >= 2" unless n >= 2
  result = []
  begin
    q = CantorPairingFunction.cantor_pairing_inv_q(c)
    y = c - CantorPairingFunction.cantor_pairing_inv_f(q)
    x = q - y
    result.unshift y
    c = x
    n -= 1
  end until n <= 1
  result.unshift x
end