Skip to content

Instantly share code, notes, and snippets.

@andrejbauer

andrejbauer/Bijection.md

Last active November 29, 2023 22:05
Show Gist options
  • Save andrejbauer/801dc7a516f5de3021cc to your computer and use it in GitHub Desktop.
Save andrejbauer/801dc7a516f5de3021cc to your computer and use it in GitHub Desktop.
Download ZIP
A bijection between numbers and pairs of numbers.
Raw
bijection.hs
-- A bijection between numbers and pairs of numbers
import Data.Bits
f :: Integer -> (Integer, Integer)
f n = loop 0 0 0 n
where loop i j k 0 = (i, j)
loop i j k n = loop i' j' (k+1) (n `shiftR` 2)
where i' = if testBit n 0 then i `setBit` k else i
j' = if testBit n 1 then j `setBit` k else j
g :: (Integer, Integer) -> Integer
g (i, j) = loop 0 0 i j
where loop n k 0 0 = n
loop n k i j = loop n'' (k+2) (i `shiftR` 1) (j `shiftR` 1)
where n' = if testBit i 0 then n `setBit` k else n
n'' = if testBit j 0 then n' `setBit` (k+1) else n'
Raw
Bijection.md

A bijection between numbers and pairs of numbers

Every once in a while I am faced with someone who denies that the rational numbers (or fractions, or pairs of integers) can be put into a bijective correspondence with natural numbers. To deal with the situation, I coded up the bijection. So now I can just say: "Really? Interesting. Please provide a pair of numbers (i,j) which is not enumerated by f, as defined in my gist." I am still waiting for a valid counter-example.

Anyhow, here is a demo of f and g at work. I am using the Python version, but a Haskell variant is included as well.

The 100-th pair is:

>>> f(100)
(10, 4)

Here are the first 50 pairs:

>>> [f(k) for k in range(50)]
[(0, 0), (1, 0), (0, 1), (1, 1), (2, 0), (3, 0), (2, 1), (3, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 2), (3, 2), (2, 3), (3, 3), (4, 0), (5, 0), (4, 1), (5, 1), (6, 0), (7, 0), (6, 1), (7, 1), (4, 2), (5, 2), (4, 3), (5, 3), (6, 2), (7, 2), (6, 3), (7, 3), (0, 4), (1, 4), (0, 5), (1, 5), (2, 4), (3, 4), (2, 5), (3, 5), (0, 6), (1, 6), (0, 7), (1, 7), (2, 6), (3, 6), (2, 7), (3, 7), (4, 4), (5, 4)]

And the first 1000 pairs:

>>> [f(k) for k in range(1000)]
[(0, 0), (1, 0), (0, 1), (1, 1), (2, 0), (3, 0), (2, 1), (3, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 2), (3, 2), (2, 3), (3, 3), (4, 0), (5, 0), (4, 1), (5, 1), (6, 0), (7, 0), (6, 1), (7, 1), (4, 2), (5, 2), (4, 3), (5, 3), (6, 2), (7, 2), (6, 3), (7, 3), (0, 4), (1, 4), (0, 5), (1, 5), (2, 4), (3, 4), (2, 5), (3, 5), (0, 6), (1, 6), (0, 7), (1, 7), (2, 6), (3, 6), (2, 7), (3, 7), (4, 4), (5, 4), (4, 5), (5, 5), (6, 4), (7, 4), (6, 5), (7, 5), (4, 6), (5, 6), (4, 7), (5, 7), (6, 6), (7, 6), (6, 7), (7, 7), (8, 0), (9, 0), (8, 1), (9, 1), (10, 0), (11, 0), (10, 1), (11, 1), (8, 2), (9, 2), (8, 3), (9, 3), (10, 2), (11, 2), (10, 3), (11, 3), (12, 0), (13, 0), (12, 1), (13, 1), (14, 0), (15, 0), (14, 1), (15, 1), (12, 2), (13, 2), (12, 3), (13, 3), (14, 2), (15, 2), (14, 3), (15, 3), (8, 4), (9, 4), (8, 5), (9, 5), (10, 4), (11, 4), (10, 5), (11, 5), (8, 6), (9, 6), (8, 7), (9, 7), (10, 6), (11, 6), (10, 7), (11, 7), (12, 4), (13, 4), (12, 5), (13, 5), (14, 4), (15, 4), (14, 5), (15, 5), (12, 6), (13, 6), (12, 7), (13, 7), (14, 6), (15, 6), (14, 7), (15, 7), (0, 8), (1, 8), (0, 9), (1, 9), (2, 8), (3, 8), (2, 9), (3, 9), (0, 10), (1, 10), (0, 11), (1, 11), (2, 10), (3, 10), (2, 11), (3, 11), (4, 8), (5, 8), (4, 9), (5, 9), (6, 8), (7, 8), (6, 9), (7, 9), (4, 10), (5, 10), (4, 11), (5, 11), (6, 10), (7, 10), (6, 11), (7, 11), (0, 12), (1, 12), (0, 13), (1, 13), (2, 12), (3, 12), (2, 13), (3, 13), (0, 14), (1, 14), (0, 15), (1, 15), (2, 14), (3, 14), (2, 15), (3, 15), (4, 12), (5, 12), (4, 13), (5, 13), (6, 12), (7, 12), (6, 13), (7, 13), (4, 14), (5, 14), (4, 15), (5, 15), (6, 14), (7, 14), (6, 15), (7, 15), (8, 8), (9, 8), (8, 9), (9, 9), (10, 8), (11, 8), (10, 9), (11, 9), (8, 10), (9, 10), (8, 11), (9, 11), (10, 10), (11, 10), (10, 11), (11, 11), (12, 8), (13, 8), (12, 9), (13, 9), (14, 8), (15, 8), (14, 9), (15, 9), (12, 10), (13, 10), (12, 11), (13, 11), (14, 10), (15, 10), (14, 11), (15, 11), (8, 12), (9, 12), (8, 13), (9, 13), (10, 12), (11, 12), (10, 13), (11, 13), (8, 14), (9, 14), (8, 15), (9, 15), (10, 14), (11, 14), (10, 15), (11, 15), (12, 12), (13, 12), (12, 13), (13, 13), (14, 12), (15, 12), (14, 13), (15, 13), (12, 14), (13, 14), (12, 15), (13, 15), (14, 14), (15, 14), (14, 15), (15, 15), (16, 0), (17, 0), (16, 1), (17, 1), (18, 0), (19, 0), (18, 1), (19, 1), (16, 2), (17, 2), (16, 3), (17, 3), (18, 2), (19, 2), (18, 3), (19, 3), (20, 0), (21, 0), (20, 1), (21, 1), (22, 0), (23, 0), (22, 1), (23, 1), (20, 2), (21, 2), (20, 3), (21, 3), (22, 2), (23, 2), (22, 3), (23, 3), (16, 4), (17, 4), (16, 5), (17, 5), (18, 4), (19, 4), (18, 5), (19, 5), (16, 6), (17, 6), (16, 7), (17, 7), (18, 6), (19, 6), (18, 7), (19, 7), (20, 4), (21, 4), (20, 5), (21, 5), (22, 4), (23, 4), (22, 5), (23, 5), (20, 6), (21, 6), (20, 7), (21, 7), (22, 6), (23, 6), (22, 7), (23, 7), (24, 0), (25, 0), (24, 1), (25, 1), (26, 0), (27, 0), (26, 1), (27, 1), (24, 2), (25, 2), (24, 3), (25, 3), (26, 2), (27, 2), (26, 3), (27, 3), (28, 0), (29, 0), (28, 1), (29, 1), (30, 0), (31, 0), (30, 1), (31, 1), (28, 2), (29, 2), (28, 3), (29, 3), (30, 2), (31, 2), (30, 3), (31, 3), (24, 4), (25, 4), (24, 5), (25, 5), (26, 4), (27, 4), (26, 5), (27, 5), (24, 6), (25, 6), (24, 7), (25, 7), (26, 6), (27, 6), (26, 7), (27, 7), (28, 4), (29, 4), (28, 5), (29, 5), (30, 4), (31, 4), (30, 5), (31, 5), (28, 6), (29, 6), (28, 7), (29, 7), (30, 6), (31, 6), (30, 7), (31, 7), (16, 8), (17, 8), (16, 9), (17, 9), (18, 8), (19, 8), (18, 9), (19, 9), (16, 10), (17, 10), (16, 11), (17, 11), (18, 10), (19, 10), (18, 11), (19, 11), (20, 8), (21, 8), (20, 9), (21, 9), (22, 8), (23, 8), (22, 9), (23, 9), (20, 10), (21, 10), (20, 11), (21, 11), (22, 10), (23, 10), (22, 11), (23, 11), (16, 12), (17, 12), (16, 13), (17, 13), (18, 12), (19, 12), (18, 13), (19, 13), (16, 14), (17, 14), (16, 15), (17, 15), (18, 14), (19, 14), (18, 15), (19, 15), (20, 12), (21, 12), (20, 13), (21, 13), (22, 12), (23, 12), (22, 13), (23, 13), (20, 14), (21, 14), (20, 15), (21, 15), (22, 14), (23, 14), (22, 15), (23, 15), (24, 8), (25, 8), (24, 9), (25, 9), (26, 8), (27, 8), (26, 9), (27, 9), (24, 10), (25, 10), (24, 11), (25, 11), (26, 10), (27, 10), (26, 11), (27, 11), (28, 8), (29, 8), (28, 9), (29, 9), (30, 8), (31, 8), (30, 9), (31, 9), (28, 10), (29, 10), (28, 11), (29, 11), (30, 10), (31, 10), (30, 11), (31, 11), (24, 12), (25, 12), (24, 13), (25, 13), (26, 12), (27, 12), (26, 13), (27, 13), (24, 14), (25, 14), (24, 15), (25, 15), (26, 14), (27, 14), (26, 15), (27, 15), (28, 12), (29, 12), (28, 13), (29, 13), (30, 12), (31, 12), (30, 13), (31, 13), (28, 14), (29, 14), (28, 15), (29, 15), (30, 14), (31, 14), (30, 15), (31, 15), (0, 16), (1, 16), (0, 17), (1, 17), (2, 16), (3, 16), (2, 17), (3, 17), (0, 18), (1, 18), (0, 19), (1, 19), (2, 18), (3, 18), (2, 19), (3, 19), (4, 16), (5, 16), (4, 17), (5, 17), (6, 16), (7, 16), (6, 17), (7, 17), (4, 18), (5, 18), (4, 19), (5, 19), (6, 18), (7, 18), (6, 19), (7, 19), (0, 20), (1, 20), (0, 21), (1, 21), (2, 20), (3, 20), (2, 21), (3, 21), (0, 22), (1, 22), (0, 23), (1, 23), (2, 22), (3, 22), (2, 23), (3, 23), (4, 20), (5, 20), (4, 21), (5, 21), (6, 20), (7, 20), (6, 21), (7, 21), (4, 22), (5, 22), (4, 23), (5, 23), (6, 22), (7, 22), (6, 23), (7, 23), (8, 16), (9, 16), (8, 17), (9, 17), (10, 16), (11, 16), (10, 17), (11, 17), (8, 18), (9, 18), (8, 19), (9, 19), (10, 18), (11, 18), (10, 19), (11, 19), (12, 16), (13, 16), (12, 17), (13, 17), (14, 16), (15, 16), (14, 17), (15, 17), (12, 18), (13, 18), (12, 19), (13, 19), (14, 18), (15, 18), (14, 19), (15, 19), (8, 20), (9, 20), (8, 21), (9, 21), (10, 20), (11, 20), (10, 21), (11, 21), (8, 22), (9, 22), (8, 23), (9, 23), (10, 22), (11, 22), (10, 23), (11, 23), (12, 20), (13, 20), (12, 21), (13, 21), (14, 20), (15, 20), (14, 21), (15, 21), (12, 22), (13, 22), (12, 23), (13, 23), (14, 22), (15, 22), (14, 23), (15, 23), (0, 24), (1, 24), (0, 25), (1, 25), (2, 24), (3, 24), (2, 25), (3, 25), (0, 26), (1, 26), (0, 27), (1, 27), (2, 26), (3, 26), (2, 27), (3, 27), (4, 24), (5, 24), (4, 25), (5, 25), (6, 24), (7, 24), (6, 25), (7, 25), (4, 26), (5, 26), (4, 27), (5, 27), (6, 26), (7, 26), (6, 27), (7, 27), (0, 28), (1, 28), (0, 29), (1, 29), (2, 28), (3, 28), (2, 29), (3, 29), (0, 30), (1, 30), (0, 31), (1, 31), (2, 30), (3, 30), (2, 31), (3, 31), (4, 28), (5, 28), (4, 29), (5, 29), (6, 28), (7, 28), (6, 29), (7, 29), (4, 30), (5, 30), (4, 31), (5, 31), (6, 30), (7, 30), (6, 31), (7, 31), (8, 24), (9, 24), (8, 25), (9, 25), (10, 24), (11, 24), (10, 25), (11, 25), (8, 26), (9, 26), (8, 27), (9, 27), (10, 26), (11, 26), (10, 27), (11, 27), (12, 24), (13, 24), (12, 25), (13, 25), (14, 24), (15, 24), (14, 25), (15, 25), (12, 26), (13, 26), (12, 27), (13, 27), (14, 26), (15, 26), (14, 27), (15, 27), (8, 28), (9, 28), (8, 29), (9, 29), (10, 28), (11, 28), (10, 29), (11, 29), (8, 30), (9, 30), (8, 31), (9, 31), (10, 30), (11, 30), (10, 31), (11, 31), (12, 28), (13, 28), (12, 29), (13, 29), (14, 28), (15, 28), (14, 29), (15, 29), (12, 30), (13, 30), (12, 31), (13, 31), (14, 30), (15, 30), (14, 31), (15, 31), (16, 16), (17, 16), (16, 17), (17, 17), (18, 16), (19, 16), (18, 17), (19, 17), (16, 18), (17, 18), (16, 19), (17, 19), (18, 18), (19, 18), (18, 19), (19, 19), (20, 16), (21, 16), (20, 17), (21, 17), (22, 16), (23, 16), (22, 17), (23, 17), (20, 18), (21, 18), (20, 19), (21, 19), (22, 18), (23, 18), (22, 19), (23, 19), (16, 20), (17, 20), (16, 21), (17, 21), (18, 20), (19, 20), (18, 21), (19, 21), (16, 22), (17, 22), (16, 23), (17, 23), (18, 22), (19, 22), (18, 23), (19, 23), (20, 20), (21, 20), (20, 21), (21, 21), (22, 20), (23, 20), (22, 21), (23, 21), (20, 22), (21, 22), (20, 23), (21, 23), (22, 22), (23, 22), (22, 23), (23, 23), (24, 16), (25, 16), (24, 17), (25, 17), (26, 16), (27, 16), (26, 17), (27, 17), (24, 18), (25, 18), (24, 19), (25, 19), (26, 18), (27, 18), (26, 19), (27, 19), (28, 16), (29, 16), (28, 17), (29, 17), (30, 16), (31, 16), (30, 17), (31, 17), (28, 18), (29, 18), (28, 19), (29, 19), (30, 18), (31, 18), (30, 19), (31, 19), (24, 20), (25, 20), (24, 21), (25, 21), (26, 20), (27, 20), (26, 21), (27, 21), (24, 22), (25, 22), (24, 23), (25, 23), (26, 22), (27, 22), (26, 23), (27, 23), (28, 20), (29, 20), (28, 21), (29, 21), (30, 20), (31, 20), (30, 21), (31, 21), (28, 22), (29, 22), (28, 23), (29, 23), (30, 22), (31, 22), (30, 23), (31, 23), (16, 24), (17, 24), (16, 25), (17, 25), (18, 24), (19, 24), (18, 25), (19, 25), (16, 26), (17, 26), (16, 27), (17, 27), (18, 26), (19, 26), (18, 27), (19, 27), (20, 24), (21, 24), (20, 25), (21, 25), (22, 24), (23, 24), (22, 25), (23, 25), (20, 26), (21, 26), (20, 27), (21, 27), (22, 26), (23, 26), (22, 27), (23, 27), (16, 28), (17, 28), (16, 29), (17, 29), (18, 28), (19, 28), (18, 29), (19, 29), (16, 30), (17, 30), (16, 31), (17, 31), (18, 30), (19, 30), (18, 31), (19, 31), (20, 28), (21, 28), (20, 29), (21, 29), (22, 28), (23, 28), (22, 29), (23, 29), (20, 30), (21, 30), (20, 31), (21, 31), (22, 30), (23, 30), (22, 31), (23, 31), (24, 24), (25, 24), (24, 25), (25, 25), (26, 24), (27, 24), (26, 25), (27, 25), (24, 26), (25, 26), (24, 27), (25, 27), (26, 26), (27, 26), (26, 27), (27, 27), (28, 24), (29, 24), (28, 25), (29, 25), (30, 24), (31, 24), (30, 25), (31, 25), (28, 26), (29, 26), (28, 27), (29, 27), (30, 26), (31, 26), (30, 27), (31, 27), (24, 28), (25, 28), (24, 29), (25, 29), (26, 28), (27, 28), (26, 29), (27, 29)]

We can draw the path in the plane that traces out the above enumeration of the first 1000 pairs:

How cool is that? We seem to have a space-filling curve! And here is an animation, just to be even cooler:

(Both images were generated with Mathematica.)

We can ask "what number corresponds to the pair (13,33)?"

>>> g((13, 33))
2131

So, this means that if we compute the 2131-th pair we should get (13,33):

>>> f(2131)
(13, 33)

In general, if we compute f(g((i,j))) we should get back (i,j):

>>> f(g((77777777777777, 66666)))
(77777777777777, 66666)

Conversely, if we compute g(f(n)) we should get back n:

>>> g(f(10000000000000000000000000000000000000000000000000000000000000000000000000000000000))
10000000000000000000000000000000000000000000000000000000000000000000000000000000000L

The functions work fast for large numbers also:

>>> f(10000000000000000000000000000000000000000000000000000000000000000000000000000000000)
(162379375244116960827628438287064410095616L, 1010220226079477904636826356504852430848L)

I mean, large numbers:

>>> f(9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999)
(151883003916807570614504085679898249156254033885476059846650722158924044951090352119090499511231495009322219166058436613210176049223198075005774889535435835656806477074726054759099196139675930421079462043202609129741999448322634554340175225773326733910074802155277549863731822738342954803166966361666573055244645149947467028134325080123242268088542115128911195293923185840977737727261247176265880548179574636936279270798565844343804845600236864779402796507297731802985217317340141125321060757999913186866276153183086136434105388005791262515471214252253786819080042980257561181714740660018799980199891786733940824756089837296872950697823276946861269556440115418990182230665748428353415423421914073696515843999642856390619233222128950893409310744319345869262823866247675238302769989121935237154091955543095464735746023747485695L, 29058257545510121024087922078086640636697632999948555337017405393124931281155476883534512422120951078230359514792826011676646247239174289340524968288486312494113540905420203850826361461273269785900259630079875960981447318769804313322760398766403276661785680543848640635478647780192941669553225884714967435553108612039399914864193455547034883115634673518714148112092657414372556763365781416831223225979425354933379376927320270880777328845429783328901224216502660715647424043837252842789220301249003917736415106359299017095483208438773510902528972211398681742183145906072101945286447194373490889936210860906731922576401938884153686881624354145618468009322965222022566550025308752401432040619524457999232654454205929716480634660041888504315094570033021395049415012698323189781393851225465452421347741272000442813799492508188671L)

Actually, that was a small number as far as computers are concerned.

Let us check that g(f(k)) equals k for the first one million values of k:

>>> range(1000000) == [g(f(k)) for k in range(1000000)]
True

Of course, this is no proof, it is just a test.

Raw
bijection.py
# The following two functions implement a bijection between
# natural numbers N and pairs of natural numbers N x N.
# The bijection is implemented efficiently by interleaving bits.
def f(n):
"""Compute the n-th pair of non-negative integers."""
i = 0
j = 0
k = 1
while n > 0:
if n & 1 == 1: i = i + k
n = n >> 1
if n & 1 == 1: j = j + k
n = n >> 1
k = k << 1
return (i,j)
def g(p):
"""Compute the index of a pair of non-negative integers."""
(i, j) = p
n = 0
k = 1
while i > 0 or j > 0:
if i & 1 == 1: n = n + k
k = k << 1
if j & 1 == 1: n = n + k
k = k << 1
i = i >> 1
j = j >> 1
return n
@olivierverdier
Copy link

Such an interleaving bit strategy seems to be called a "Morton code", or "Z-order curve": http://www.wikiwand.com/en/Z-order_curve

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment