Design a commutative injective function between any (restricted) infinite set and unordered pairs thereof

Question

Related, but this only requires positive integers and does not have to be commutative

The Cantor Pairing Function is described in this Wikipedia article. Essentially, it is an operation such that when it is applied to two values X and Y, one can obtain the original values X and Y given the result.

Your task is to design two functions: one which performs X, Y -> Z and the other which performs Z -> X, Y. Here's the catch: X, Y -> Z must be commutative. This means that Z -> X, Y won't be able to determine if the input was X, Y or Y, X.

The formal definition of this challenge would be:

Choose an countable infinite set S of numbers.
Design two functions that perform the following tasks:

• Given an unordered pair of values in S, return a value in S
• Given a return value from the initial function, return the unordered pair of values which evaluates to the input integer when passed through the first function. I don't care about the behaviour of this inverse function if the input isn't a return value from the first function.

Requirements

• The result should be identical between runs.
• {a, a} is an unordered pair

Note: your answer is more likely to get an upvote from me if you provide a proof, but I will test answers when I get to it and upvote it once I'm fairly sure it works.

Answer 1

Haskell, 65 + 30 = 95 bytes

a#b=length.fst$span(<(max a b,min a b))[(a,b)|a<-[1..],b<-[1..a]]

Try it online!

([(a,b)|a<-[1..],b<-[1..a]]!!)

Try it online!

---

Note: When the two functions may share code, this is only 75 bytes:

(l!!)
a#b=length.fst$span(<(max a b,min a b))l
l=[(a,b)|a<-[1..],b<-[1..a]]

Try it online! The domain is the positive integers. The function (#) performs the pairing, the function (l!!) its inverse. Usage example: Both (#) 5 3 and (#) 3 5 yield 12, and (l!!) 12 yields (5,3).

This works by explicitly listing all sorted pairs in an infinite list l:

l = [(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4),(5,5),(6,1), ...`

The encoding is then just the index in this list.

Answer 2

Pyth, 8 + 6 = 14 bytes

ij\aSQ16

    SQ   # Sort the input
 j\a     # join with "a"
i     16 # convert from base 16 to base 10

Try it online!

c.HQ\a

 .HQ     # convert from base 10 to 16
c   \a   # split on "a"

Try it online!
Domain: Positive integers.

Answer 3

Jelly, 8 + 11 = 19 bytes

Rolled back since Rod's algorithm didn't work.

This works on the domain of the positive integers.

Takes x and y as 2 arguments, doesn't matter in which order, returns z.

»’RSð+ð«

Try it online!

Takes z and returns [min(x, y), max(x, y)]

R€Ẏ,Rx`$ị@€

Try it online!

Answer 4

C (gcc), 36 + 39 = 75 bytes

Thanks to @tsh for saving two bytes.

The domain is non-negative integers.

p(x,y){return y>x?p(y,x):-~x*x/2+y;}

Takes x and y, returns z.

u(int*r){for(*r=0;r[1]>*r;r[1]-=++*r);}

Takes a two-element int array. The second element must be set to z before the call. After the call r contains x and y.

Try it online!

Answer 5

JavaScript (ES7), 44 bytes

(x,y)=>x>y?x*x+y:y*y+x
z=>[x=z**.5|0,y=z-x*x]

Maps from non-negative integers to a subset thereof.

Answer 6

Jelly, 13 11 bytes

pair of positive integers to positive integer, 5 bytes

Ṁc2+Ṃ

Try it online!

positive integer to pair of positive integers, 6 bytes

ŒċṀÞị@

Try it online!

Algorithm

If we sort the set of all unordered pairs of positive integers by their maximum and then by their sum, we get the following sequence.

{1,1}, {1,2}, {2,2}, {1,3}, {2,3}, {3,3}, {1,4}, {2,4}, {3,4}, {4,4}, {1,5}, {2,5}, {3,5}, {4,5}, {5,5}, …

The first function takes a pair {x,y} and finds its index in this sequence.

The second function takes a positive integer z and returns the z^th item of the sequence.

Note that this mapping is the same as in @EriktheOutgolfer's Jelly answer.

How it works

Ṁc2+Ṃ   Main link. Argument: [x, y]
        Let m = max(x, y) and n = min(x, y).

Ṁ       Maximum; yield m.
 c2     2-combinations; yield mC2 = m(m-1)/2.
        Note that there's one pair with maximum 1 ({1,1}), two pairs with maximum 2
        ({1,2}, {2,2}), etc., so there are 1 + 2 + … + (m-1) = m(m-1)/2 pairs with
        maximum less than m.
    Ṃ   Minimum; yield n.
        Note that {x,y} is the n-th pair with maximum m.
   +    Add; yield mC2 + n.
        This finds {x,y}'s index in the sequence.

ŒċṀÞị@  Main link. Argument: z

Œċ      2-combinations w/replacement; yield all pairs [x, y] such that x ≤ y ≤ z.
  ṀÞ    Sort by maximum.
    ị@  Retrieve the pair at index z (1-based).

Answer 7

Mathematica (35+53)=78 Bytes

((x=Min[#])+(y=Max[#]))(x+y+1)/2+y&

(i=Floor[(-1+Sqrt[1+8#])/2];{#-i(1+i)/2,i(3+i)/2-#})&

This is the one good known quadratic pairing function for Z<-->ZxZ combined with Min and Max to make it orderless.

Answer 8

Java 8, 153 146 141 137 + 268 224 216 205 bytes

Pair function

a->{String f="";for(int i=(f+a[0]).length(),c=0,j;i>0;i-=c,f+=c,c=0)for(j=1;j<10;c+=i-j++<0?0:1);return new Integer(a[0]+""+a[1]+"0"+f);}

Try it online!

Depair function

r->{String a=r+"",t=a.substring(a.lastIndexOf('0')+1);int l=0,i=l,o=t.length();for(;i<o;l+=r.decode(t.charAt(i++)+""));return new int[]{r.decode(a.substring(0,l)),r.decode(a.substring(l,a.length()-o-1))};}

Try it online!

Answer 9

Ruby, 66 bytes

f=->x,y{2**~-x|2**~-y}
g=->n{x,y=(1..n).select{|i|n[i-1]>0};[x,y||x]}

I'm trying to find a way to cunningly select an infinite set to make this easier, this is the best I've got so far.

We define f(x,y) = 2^x-1 bitwise-or 2^y-1. The domain consists of the set defined recursively as containing 1,2, and all numbers that can be produced by calling f on numbers in the set (note that f(1,1) = 1 and f(2,2) = 2, so 1 and 2 have inverses). The resulting numbers all have either one or two 1s in their binary expansion, with the indices of the 1s corresponding to numbers in the set. We can get the original unordered pair out by taking the indices. If there's only one 1, that means the elements of the pair are equal.

For example, f(3,5) is 20, because 20 is 10100 in base 2, which has 1s in the 3rd and 5th least significant places.

Answer 10

05AB1E, 6 + 11 = 17 bytes

Port of my Jelly answer.

Domain: positive integers.

Takes a list [x, y] as input, returns z.

{`<LO+

Try it online!

Takes a positive integer z as input, returns [min(x, y), max(x, y)].

L2ã€{RÙR¹<è

Try it online!

-5 thanks to Emigna.

Answer 11

JavaScript, 72 bytes

f=a=>eval('0x'+a.sort().join`a`)
g=n=>n.toString(16).split`a`.map(x=>+x)

Works for positive integers (in theory). Quite simple idea: sort two number in some (magic) order, connect them as string by a letter "a", parse it as hex integer.

f=a=>eval('0x'+a.sort().join`a`)
g=n=>n.toString(16).split`a`.map(x=>+x)

<pre oninput="p.value=f([+x.value, +y.value])">
     X = <input id="x" type="number" min="0" />
     Y = <input id="y" type="number" min="0" />
 f(X,Y)= <output id="p"></output>
</pre>

<pre oninput="q.value=g(+u.value).join(', ')">
     U = <input id="u" type="number" />
   g(U)= <output id="q"></output>
</pre>

Answer 12

MATL, 6+8=14 bytes

Encoding function, takes two inputs n, m. Outputs product of nth prime and mth prime.

,iYq]*

Steps:

• , - Do twice
• i - Push input
• Yq - Pop input, push input'th prime
• ]* - End do twice, pop both primes and push product

---

Decoding function, takes one input m. Outputs the number of primes below each of the prime factors of n.

iYf"@Zqn

Steps:

• i - Push input
• Yf - Pop input, push array of prime factors
• " - For n in array
• @Zq - Push array of primes below n
• n - Pop array, push length of array

This is commutative because multiplication is commutative, and injective because prime factorizations are unique. Not that this is not onto the integers.

Answer 13

Husk, 5+3=8 bytes

I really hope I got the challenge right, I see some deleted answers that seem valid to me...

Couples of positive integers to a single positive integer:

¤*!İp

Try it online!

It works by taking the numbers at the given indices (1-indexed) from the list of prime numbers, and multiplying them.

Result of the first function to couples of positive integers:

mṗp

Try it online!

We factorize the input number and return the index in the list of primes of all (both) of its factors.

Worked example

Given (4,1) as a starting couple, we take the fourth and first prime numbers (7,2) and multiply them → 14. This multiplication is what makes the function indipendent on the order of the two elements.

Starting from 14, we factorize it (2,7) and return the indices of 2 and 7 in the list of prime numbers → (1,4).

Answer 14

C#, 80 bytes ( 38 + 42 )

---

Data

Encoder

• Input Int32 l A number
• Input Int32 r A number
• Output Int64 Both ints fused together

Decoder

• Input Int32 v The value
• Output Int32[] An array with the two original ints.

---

Golfed

// Encoder
e=(l,r)=>{return(long)l<<32|(uint)r;};

// Decoder
d=v=>{return new[]{v>>32,v&0xFFFFFFFFL};};

---

Ungolfed

// Encoder
e = ( l, r ) => {
    return (long) l << 32 | (uint) r;
};

// Decoder
d = v => {
    return new[] {
        v >> 32,
        v & 0xFFFFFFFFL };
};

---

Ungolfed readable

// Encoder
// Takes a pair of ints
e = ( l, r ) => {

    // Returns the ints fused together in a long where the first 32 bits are the first int
    // and the last 32 bits the second int
    return (long) l << 32 | (uint) r;
};

// Decoder
// Takes a long
d = v => {

    // Returns an array with the ints decoded where...
    return new[] {

        // ... the first 32 bits are the first int...
        v >> 32,

        // ... and the last 32 bits the second int
        v & 0xFFFFFFFFL };
};

---

Full code

using System;
using System.Collections.Generic;

namespace TestBench {
    public class Program {
        // Methods
        static void Main( string[] args ) {
            Func<Int32, Int32, Int64> e = ( l, r ) => {
                return(long) l << 32 | (uint) r;
            };
            Func<Int64, Int64[]> d = v => {
                return new[] { v >> 32, v & 0xFFFFFFFFL };
            };

            List<KeyValuePair<Int32, Int32>>
                testCases = new List<KeyValuePair<Int32, Int32>>() {
                    new KeyValuePair<Int32, Int32>( 13, 897 ),
                    new KeyValuePair<Int32, Int32>( 54234, 0 ),
                    new KeyValuePair<Int32, Int32>( 0, 0 ),
                    new KeyValuePair<Int32, Int32>( 1, 1 ),
                    new KeyValuePair<Int32, Int32>( 615234, 1223343 ),
                };

            foreach( KeyValuePair<Int32, Int32> testCase in testCases ) {
                Console.WriteLine( $" ENCODER: {testCase.Key}, {testCase.Value} = {e( testCase.Key, testCase.Value )}" );
                Console.Write( $"DECODING: {e( testCase.Key, testCase.Value )} = " );
                PrintArray( d( e( testCase.Key, testCase.Value ) ) );

                Console.WriteLine();
            }

            Console.ReadLine();
        }

        public static void PrintArray<TSource>( TSource[] array ) {
            PrintArray( array, o => o.ToString() );
        }
        public static void PrintArray<TSource>( TSource[] array, Func<TSource, String> valueFetcher ) {
            List<String>
                output = new List<String>();

            for( Int32 index = 0; index < array.Length; index++ ) {
                output.Add( valueFetcher( array[ index ] ) );
            }

            Console.WriteLine( $"[ {String.Join( ", ", output )} ]" );
        }
    }
}

---

Releases

• v1.0 - 80 bytes - Initial solution.

---

Notes

• None

Answer 15

Python: 41+45=86

encoder: 41

e=lambda*x:int('1'*max(x)+'0'+'1'*min(x))

e(4, 3), e(3,4)

(11110111, 11110111)

decoder: 45

d=lambda z:[len(i)for i in str(z).split('0')]

d(11110111)

[4, 3]

Older attempt:

Python: 114: 30 + 84

encoder: 30

accepts 2 integers, returns a string

e=lambda*x:2**max(x)*3**min(x)

e(3, 4), e(4, 3)

(432, 432)

decoder: 86

def d(z):
 x=y=0
 while 1-z%2:
  x+=1
  z/=2
 while 1-z%3:
  y+=1
  z/=3
 return x,y

d(432)

4, 3

decoder2: 120

another attempt with generator comprehensions and sum

def d(z):
 x=sum(1 for i in range(z)if not z%(2**i))-1
 z/=2**x
 return x,sum(1 for i in range(int(z))if not z%(3**i))-1