18
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Doesn't this fit better for puzzling.stackexchange.com? \$\endgroup\$ – Jakube Sep 11 '17 at 13:13
  • 2
    \$\begingroup\$ @Jakube Not necessarily, as you are required to write code. \$\endgroup\$ – Mr. Xcoder Sep 11 '17 at 13:13
  • \$\begingroup\$ I'm assuming pairs are unique, but the numbers used in those pairs are not? So when 1,2 is one of the pairs, 1,3 can also be a potential pair (both use 1)? \$\endgroup\$ – Kevin Cruijssen Sep 11 '17 at 13:38
  • \$\begingroup\$ @KevinCruijssen I'm not sure what you mean \$\endgroup\$ – HyperNeutrino Sep 11 '17 at 13:48
  • \$\begingroup\$ @Giuseppe The inverse does not need to be able to return the correct order; it's just that for function f and its inverse g, sorted((x, y)) should be the same as sorted(g(f(x, y))) \$\endgroup\$ – HyperNeutrino Sep 11 '17 at 13:49

15 Answers 15

13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ by the OP, shared code must be counted twice \$\endgroup\$ – proud haskeller Sep 11 '17 at 21:26
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ nice approach! +1 \$\endgroup\$ – HyperNeutrino Sep 11 '17 at 14:39
  • 4
    \$\begingroup\$ Doesn't work for a lot of numbers like 2 and 10 for example (which are in the domain) \$\endgroup\$ – Emigna Sep 11 '17 at 14:47
  • \$\begingroup\$ Sure. Example1, Example2 \$\endgroup\$ – Emigna Sep 11 '17 at 14:51
  • \$\begingroup\$ The 2nd function is supposed to work for any value in S, not just one that was generated with the first function (I made the same mistake). \$\endgroup\$ – Arnauld Sep 11 '17 at 14:53
4
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Why the downvotes? This isn't Rod's algorithm. \$\endgroup\$ – Erik the Outgolfer Sep 11 '17 at 18:04
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ (x+1) -> -~x \$\endgroup\$ – tsh Sep 12 '17 at 7:04
3
\$\begingroup\$

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 zth 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).
\$\endgroup\$
  • 2
    \$\begingroup\$ Explanation please. I'm not confident this is valid... \$\endgroup\$ – Erik the Outgolfer Sep 11 '17 at 15:42
  • \$\begingroup\$ I've added the algorithm. \$\endgroup\$ – Dennis Sep 11 '17 at 15:54
  • \$\begingroup\$ Something doesn't stick well to me...although I'm not sure if this is invalid either. Basically it kind of doesn't stick well that you use both c and Œċ...although I may be wrong. BTW that was my answer that you outgolfed >_> \$\endgroup\$ – Erik the Outgolfer Sep 11 '17 at 18:03
  • \$\begingroup\$ The difference is minimal for pairs. If C computes combinations without replacement and Ƈ computes combinations with, nƇ2 = nC2 + n. \$\endgroup\$ – Dennis Sep 11 '17 at 18:19
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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) = 2x-1 bitwise-or 2y-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.

\$\endgroup\$
  • \$\begingroup\$ S=this set (OEIS link) \$\endgroup\$ – Giuseppe Sep 11 '17 at 20:10
  • \$\begingroup\$ Thanks, S is actually a subset of that OEIS sequence though because it only includes numbers whose 1s have indexes in S. \$\endgroup\$ – histocrat Sep 11 '17 at 20:18
  • \$\begingroup\$ ah yes, of course. Well, no other sequence matches the first few terms (up to 32). \$\endgroup\$ – Giuseppe Sep 11 '17 at 20:32
  • \$\begingroup\$ Add 0 to S and you can save a few decrements. \$\endgroup\$ – nwellnhof Sep 11 '17 at 21:55
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can golf a few parts. In the pair function: int i=(""+a[0]).length() can be int i=(f+a[0]).length(); the space between c=0,j;i>0; can be removed; a[0].parseInt can be new Integer. In the depair function: all three r.parseInt can be r.decode; and you could make an int variable for t.length(), since you use it twice. \$\endgroup\$ – Kevin Cruijssen Sep 12 '17 at 7:40
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your second program can save 5 bytes with L2ã€{RÙRI<è \$\endgroup\$ – Emigna Sep 11 '17 at 15:33
  • \$\begingroup\$ @Emigna Nice trick with 2ã€{RÙR! \$\endgroup\$ – Erik the Outgolfer Sep 11 '17 at 15:39
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Actually, looking at the deleted answer from Arnauld, its algorithm is even better, and porting it to Husk would result in 6 bytes... Could someone confirm whether its solution (and mine too) is valid or not? \$\endgroup\$ – Leo Sep 12 '17 at 7:22
  • \$\begingroup\$ Doesn't work for primes (which are in the domain of positive integers) \$\endgroup\$ – Emigna Sep 12 '17 at 8:35
  • \$\begingroup\$ @Emigna the second function doesn't, but primes are never returned by the first one... \$\endgroup\$ – Leo Sep 12 '17 at 9:23
  • \$\begingroup\$ Your domain is positive integers, so both methods need to work for positive integers. EDIT: or at least that used to be a requirement. The current rules seem to allow a subset of the domain. \$\endgroup\$ – Emigna Sep 12 '17 at 9:42
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ based on second attempt: e=lambda*x:10**sum(x)-10**min(x);d=lambda z:map(z.count,'09'); TIO \$\endgroup\$ – tsh Sep 13 '17 at 5:14
  • \$\begingroup\$ @tsh very nice. I will adapt it later, or you can submit your own answer \$\endgroup\$ – Maarten Fabré Sep 13 '17 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.