Last active
November 26, 2024 01:22
-
-
Save ma11hew28/9457506 to your computer and use it in GitHub Desktop.
Unique Unordered Pairing Function
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ ruby unique-unordered-pairing-function.rb | |
Cantor Pairing Function | |
----------------------- | |
<x, y> = (x + y) * (x + y + 1) / 2 + y | |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
0 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 | 78 | 91 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
1 | 2 | 4 | 7 | 11 | 16 | 22 | 29 | 37 | 46 | 56 | 67 | 79 | 92 | 106 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
2 | 5 | 8 | 12 | 17 | 23 | 30 | 38 | 47 | 57 | 68 | 80 | 93 | 107 | 122 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
3 | 9 | 13 | 18 | 24 | 31 | 39 | 48 | 58 | 69 | 81 | 94 | 108 | 123 | 139 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
4 | 14 | 19 | 25 | 32 | 40 | 49 | 59 | 70 | 82 | 95 | 109 | 124 | 140 | 157 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
5 | 20 | 26 | 33 | 41 | 50 | 60 | 71 | 83 | 96 | 110 | 125 | 141 | 158 | 176 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
6 | 27 | 34 | 42 | 51 | 61 | 72 | 84 | 97 | 111 | 126 | 142 | 159 | 177 | 196 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
7 | 35 | 43 | 52 | 62 | 73 | 85 | 98 | 112 | 127 | 143 | 160 | 178 | 197 | 217 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
8 | 44 | 53 | 63 | 74 | 86 | 99 | 113 | 128 | 144 | 161 | 179 | 198 | 218 | 239 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
9 | 54 | 64 | 75 | 87 | 100 | 114 | 129 | 145 | 162 | 180 | 199 | 219 | 240 | 262 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
10 | 65 | 76 | 88 | 101 | 115 | 130 | 146 | 163 | 181 | 200 | 220 | 241 | 263 | 286 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
11 | 77 | 89 | 102 | 116 | 131 | 147 | 164 | 182 | 201 | 221 | 242 | 264 | 287 | 311 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
12 | 90 | 103 | 117 | 132 | 148 | 165 | 183 | 202 | 222 | 243 | 265 | 288 | 312 | 337 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
13 | 104 | 118 | 133 | 149 | 166 | 184 | 203 | 223 | 244 | 266 | 289 | 313 | 338 | 364 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
Unordered Pairing Function | |
-------------------------- | |
<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x> | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
1 | 1 | 2 | 3 | 5 | 7 | 10 | 13 | 17 | 21 | 26 | 31 | 37 | 43 | 50 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
2 | 2 | 4 | 6 | 8 | 11 | 14 | 18 | 22 | 27 | 32 | 38 | 44 | 51 | 58 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
3 | 3 | 6 | 9 | 12 | 15 | 19 | 23 | 28 | 33 | 39 | 45 | 52 | 59 | 67 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
4 | 5 | 8 | 12 | 16 | 20 | 24 | 29 | 34 | 40 | 46 | 53 | 60 | 68 | 76 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
5 | 7 | 11 | 15 | 20 | 25 | 30 | 35 | 41 | 47 | 54 | 61 | 69 | 77 | 86 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
6 | 10 | 14 | 19 | 24 | 30 | 36 | 42 | 48 | 55 | 62 | 70 | 78 | 87 | 96 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
7 | 13 | 18 | 23 | 29 | 35 | 42 | 49 | 56 | 63 | 71 | 79 | 88 | 97 | 107 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
8 | 17 | 22 | 28 | 34 | 41 | 48 | 56 | 64 | 72 | 80 | 89 | 98 | 108 | 118 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
9 | 21 | 27 | 33 | 40 | 47 | 55 | 63 | 72 | 81 | 90 | 99 | 109 | 119 | 130 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
10 | 26 | 32 | 39 | 46 | 54 | 62 | 71 | 80 | 90 | 100 | 110 | 120 | 131 | 142 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
11 | 31 | 38 | 45 | 53 | 61 | 70 | 79 | 89 | 99 | 110 | 121 | 132 | 143 | 155 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
12 | 37 | 44 | 52 | 60 | 69 | 78 | 88 | 98 | 109 | 120 | 132 | 144 | 156 | 168 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
13 | 43 | 51 | 59 | 68 | 77 | 87 | 97 | 108 | 119 | 131 | 143 | 156 | 169 | 182 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
14 | 50 | 58 | 67 | 76 | 86 | 96 | 107 | 118 | 130 | 142 | 155 | 168 | 182 | 196 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
Unique Unordered Pairing Function | |
--------------------------------- | |
<x, y> = if x < y: | |
x * (y - 1) + trunc((y - x - 2)^2 / 4) | |
if x > y: | |
(x - 1) * y + trunc((x - y - 2)^2 / 4) | |
= <y, x> | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
1 | 1 | 1 | 2 | 3 | 5 | 7 | 10 | 13 | 17 | 21 | 26 | 31 | 37 | 43 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
2 | 1 | 3 | 4 | 6 | 8 | 11 | 14 | 18 | 22 | 27 | 32 | 38 | 44 | 51 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
3 | 2 | 4 | 7 | 9 | 12 | 15 | 19 | 23 | 28 | 33 | 39 | 45 | 52 | 59 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
4 | 3 | 6 | 9 | 13 | 16 | 20 | 24 | 29 | 34 | 40 | 46 | 53 | 60 | 68 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
5 | 5 | 8 | 12 | 16 | 21 | 25 | 30 | 35 | 41 | 47 | 54 | 61 | 69 | 77 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
6 | 7 | 11 | 15 | 20 | 25 | 31 | 36 | 42 | 48 | 55 | 62 | 70 | 78 | 87 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
7 | 10 | 14 | 19 | 24 | 30 | 36 | 43 | 49 | 56 | 63 | 71 | 79 | 88 | 97 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
8 | 13 | 18 | 23 | 29 | 35 | 42 | 49 | 57 | 64 | 72 | 80 | 89 | 98 | 108 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
9 | 17 | 22 | 28 | 34 | 41 | 48 | 56 | 64 | 73 | 81 | 90 | 99 | 109 | 119 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
10 | 21 | 27 | 33 | 40 | 47 | 55 | 63 | 72 | 81 | 91 | 100 | 110 | 120 | 131 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
11 | 26 | 32 | 39 | 46 | 54 | 62 | 71 | 80 | 90 | 100 | 111 | 121 | 132 | 143 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
12 | 31 | 38 | 45 | 53 | 61 | 70 | 79 | 89 | 99 | 110 | 121 | 133 | 144 | 156 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
13 | 37 | 44 | 52 | 60 | 69 | 78 | 88 | 98 | 109 | 120 | 132 | 144 | 157 | 169 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
14 | 43 | 51 | 59 | 68 | 77 | 87 | 97 | 108 | 119 | 131 | 143 | 156 | 169 | 183 | | |
+ βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + βββ + | |
Benchmarks | |
---------- | |
Rehearsal ---------------------------------------------------- | |
Cantor 0.040000 0.000000 0.040000 ( 0.040982) | |
Unordered 0.060000 0.000000 0.060000 ( 0.062546) | |
Unique Unordered 0.070000 0.000000 0.070000 ( 0.061457) | |
------------------------------------------- total: 0.170000sec | |
user system total real | |
Cantor 0.040000 0.000000 0.040000 ( 0.040904) | |
Unordered 0.060000 0.000000 0.060000 ( 0.059940) | |
Unique Unordered 0.060000 0.000000 0.060000 ( 0.061397) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def cantor_pair(x, y) | |
(x + y) * (x + y + 1) / 2 + y | |
end | |
def unordered_pair(x, y) | |
if x < y | |
x*y + (y - x - 1)**2 / 4 | |
else | |
x*y + (x - y - 1)**2 / 4 | |
end | |
end | |
def unique_unordered_pair(x, y) | |
if x < y | |
x * (y - 1) + (y - x - 2)**2 / 4 | |
else | |
(x - 1) * y + (x - y - 2)**2 / 4 | |
end | |
end | |
def print_table(start: 0) | |
stop = start + 13 | |
table = [] | |
start.upto(stop) do |y| | |
row = [] | |
start.upto(stop) do |x| | |
row[x-start] = yield(x, y) | |
end | |
table[y] = row | |
end | |
puts ' ' + (start..stop).map { |x| x.to_s.rjust(3) }.join(' ') | |
puts ' +' + ' βββ +' * (stop-start+1) | |
start.upto(stop) do |y| | |
puts y.to_s.rjust(2) + ' | ' + table[y].map { |x| x.to_s.rjust(3) }.join(' | ') + ' |' | |
puts ' +' + ' βββ +' * table[y].length | |
end | |
end | |
puts | |
puts 'Cantor Pairing Function' | |
puts '-----------------------' | |
puts | |
puts '<x, y> = (x + y) * (x + y + 1) / 2 + y' | |
puts | |
print_table { |x, y| cantor_pair(x, y) } | |
puts | |
puts | |
puts 'Unordered Pairing Function' | |
puts '--------------------------' | |
puts | |
puts '<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>' | |
puts | |
print_table(start: 1) { |x, y| unordered_pair(x, y) } | |
puts | |
puts | |
puts 'Unique Unordered Pairing Function' | |
puts '---------------------------------' | |
puts | |
puts '<x, y> = if x < y: | |
x * (y - 1) + trunc((y - x - 2)^2 / 4) | |
if x > y: | |
(x - 1) * y + trunc((x - y - 2)^2 / 4) | |
= <y, x>' | |
puts | |
print_table(start: 1) { |x, y| unique_unordered_pair(x, y) } | |
puts | |
puts | |
puts 'Benchmarks' | |
puts '----------' | |
puts | |
require 'benchmark' | |
Benchmark.bmbm do |b| | |
stop = 500 | |
b.report('Cantor') { 1.upto(stop) { |y| 1.upto(stop) { |x| cantor_pair(x, y) } } } | |
b.report('Unordered') { 1.upto(stop) { |y| 1.upto(stop) { |x| unordered_pair(x, y) } } } | |
b.report('Unique Unordered') { 1.upto(stop) { |y| 1.upto(stop) { |x| unique_unordered_pair(x, y) } } } | |
end | |
puts |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment