Powiązane, ale wymaga to tylko dodatnich liczb całkowitych i nie musi być przemienne

Funkcję parowania kantora opisano w tym artykule w Wikipedii . Zasadniczo jest to operacja taka, że ​​po zastosowaniu do dwóch wartości X i Y można uzyskać oryginalne wartości X i Y, biorąc pod uwagę wynik.

Twoim zadaniem jest zaprojektowanie dwóch funkcji: jednej, która wykonuje, X, Y -> Za drugiej, która wykonuje Z -> X, Y. Oto haczyk: X, Y -> Zmusi być przemienny. Oznacza to, że Z -> X, Ynie będzie w stanie ustalić, czy dane wejściowe były X, Ylub Y, X.

Formalna definicja tego wyzwania brzmiałaby:

Wybierz policzalny nieskończony zbiór S liczb.
Zaprojektuj dwie funkcje, które wykonują następujące zadania:

• Biorąc pod uwagę nieuporządkowaną parę wartości w S, zwróć wartość w S
• Biorąc pod uwagę wartość zwracaną z funkcji początkowej, zwróć nieuporządkowaną parę wartości, która ocenia na wejściową liczbę całkowitą po przejściu przez pierwszą funkcję. Nie obchodzi mnie zachowanie tej funkcji odwrotnej, jeśli dane wejściowe nie są wartością zwracaną z pierwszej funkcji.

Wymagania

• Wynik powinien być identyczny między seriami.
• {a, a} jest nieuporządkowaną parą

Uwaga: twoja odpowiedź jest bardziej prawdopodobna, jeśli dostaniesz ode mnie głos, jeśli dostarczysz dowód, ale przetestuję odpowiedzi, kiedy do niego dojdę, i głosuję, gdy będę dość pewny, że zadziała.

Haskell , 65 + 30 = 95 bajtów

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

Wypróbuj online!

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

Wypróbuj online!

Uwaga: Gdy dwie funkcje mogą współdzielić kod, jest to tylko 75 bajtów:

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

Wypróbuj online! Domena to dodatnie liczby całkowite. Funkcja (#)wykonuje parowanie, funkcja (l!!)jest odwrotna. Przykład użycia: Zarówno (#) 5 3i (#) 3 5plon 12, jak i (l!!) 12plon(5,3) .

Działa to poprzez jawne wyświetlanie wszystkich posortowanych par na nieskończonej liście 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), ...`

Kodowanie jest wtedy tylko indeksem na tej liście.

Pyth , 8 + 6 = 14 bajtów

ij\aSQ16

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

Wypróbuj online!

c.HQ\a

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

Wypróbuj online!
Domena: dodatnie liczby całkowite.

Galaretka , 8 + 11 = 19 bajtów

Wycofano, ponieważ algorytm Rod nie działał.

Działa to w domenie liczb całkowitych dodatnich.

Bierze xi yjako 2 argumenty, nie ma znaczenia, w jakiej kolejności zwraca z.

»’RSð+ð«

Wypróbuj online!

Bierze zi wraca[min(x, y), max(x, y)]

R€Ẏ,Rx`$ị@€

Wypróbuj online!

JavaScript (ES7), 44 bajty

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

Mapy od liczb całkowitych nieujemnych do ich podzbiorów.

C (gcc) , 36 + 39 = 75 bajtów

Dzięki @tsh za zapisanie dwóch bajtów.

Domena to nieujemne liczby całkowite.

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

Bierze xi yzwraca z.

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

Przyjmuje inttablicę dwuelementową . Drugi element musi być ustawiony zprzed wywołaniem. Po połączeniu rzawiera xi y.

Wypróbuj online!

Galaretka , 13 11 bajtów

para dodatnich liczb całkowitych do dodatniej liczby całkowitej, 5 bajtów

Ṁc2+Ṃ

Wypróbuj online!

dodatnia liczba całkowita do pary dodatnich liczb całkowitych, 6 bajtów

ŒċṀÞị@

Wypróbuj online!

Algorytm

Jeśli posortujemy zestaw wszystkich nieuporządkowanych par liczb całkowitych dodatnich według ich maksimum, a następnie według ich sumy, otrzymamy następującą sekwencję.

{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},…

Pierwsza funkcja bierze parę {x, y} i znajduje swój indeks w tej sekwencji.

Druga funkcja przyjmuje dodatnią liczbę całkowitą z i zwraca z ^th element sekwencji.

Zauważ, że to mapowanie jest takie samo jak w odpowiedzi Jelly @ EriktheOutgolfer .

Jak to działa

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

Mathematica (35 + 53) = 78 bajtów

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

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

Jest to jedna dobrze znana funkcja parowania kwadratowego dla Z <--> ZxZ w połączeniu z Min i Max, dzięki czemu jest bez porządku.

Rubin, 66 bajtów

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

Próbuję znaleźć sposób, aby sprytnie wybrać nieskończony zestaw, aby to ułatwić, jest to najlepsze, jakie do tej pory miałem.

Definiujemy f (x, y) = 2 ^x-1 bitowo-lub 2 ^y-1 . Domena składa się ze zbioru zdefiniowanego rekurencyjnie jako zawierającego 1,2 oraz wszystkich liczb, które można uzyskać, wywołując f na numerach w zestawie (zwróć uwagę, że f (1,1) = 1 i f (2,2) = 2, więc 1 i 2 mają inwersje). Wszystkie wynikowe liczby mają jeden lub dwa jedynki w rozwinięciu binarnym, przy czym indeksy jedności odpowiadają liczbom w zbiorze. Możemy wyciągnąć oryginalną nieuporządkowaną parę, biorąc indeksy. Jeśli jest tylko jeden 1, oznacza to, że elementy pary są równe.

Na przykład f (3,5) wynosi 20, ponieważ 20 to 10100 w bazie 2, która ma 1 w 3 i 5 najmniej znaczących miejscach.

Java 8, 153 146 141 137 + 268 224 216 205 bajtów

Funkcja parowania

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);}

Wypróbuj online!

Funkcja Depair

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))};}

Wypróbuj online!

05AB1E , 6 + 11 = 17 bajtów

Port mojej galaretki odpowiedzi.

Domena: dodatnie liczby całkowite.

Pobiera listę [x, y]jako dane wejściowe, zwraca z.

{`<LO+

Wypróbuj online!

Pobiera na zwejściu dodatnią liczbę całkowitą , zwraca [min(x, y), max(x, y)].

L2ã€{RÙR¹<è

Wypróbuj online!

-5 dzięki Emignie .

JavaScript, 72 bajty

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

Działa dla dodatnich liczb całkowitych (w teorii). Całkiem prosty pomysł: posortuj dwie liczby w jakiejś (magicznej) kolejności, połącz je jako ciąg literowy "a", parsuj jako liczbę całkowitą w postaci heksadecymalnej.

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>

MATL, 6 + 8 = 14 bajtów

Funkcja kodowania zajmuje dwa wejścia n, m. Produkuje iloczyn n-tej i pierwszej-tej liczby pierwszej.

,iYq]*

Kroki:

• , - Zrób dwa razy
• i - Wejście push
• Yq - Pop wejście, push wejście czwarta liczba pierwsza
• ]* - Zakończ dwa razy, pop obu liczb pierwszych i wypchnij produkt

Funkcja dekodowania zajmuje jedno wejście m. Podaje liczbę liczb pierwszych poniżej każdego z czynników pierwszych n.

iYf"@Zqn

Kroki:

• i - Wejście push
• Yf - Pop wejście, push tablica czynników pierwszych
• " - Dla nw tablicy
• @Zq - Wciśnij tablicę liczb pierwszych poniżej n
• n - Pop tablica, push długość tablicy

Jest to przemienne, ponieważ mnożenie jest przemienne, a iniekcyjne, ponieważ czynniki pierwsze są unikalne. Nie to, że nie jest to na liczbach całkowitych.

Łuska , 5 + 3 = 8 bajtów

Naprawdę mam nadzieję, że dobrze podjąłem wyzwanie. Widzę kilka usuniętych odpowiedzi, które wydają mi się ważne ...

Pary dodatnich liczb całkowitych do jednej dodatniej liczby całkowitej:

¤*!İp

Wypróbuj online!

Działa poprzez pobranie liczb z podanych indeksów (1-indeksowanych) z listy liczb pierwszych i pomnożenie ich.

Wynik pierwszej funkcji dla par dodatnich liczb całkowitych:

mṗp

Wypróbuj online!

Faktoryzujemy liczbę wejściową i zwracamy indeks na liście liczb pierwszych wszystkich (obu) jego czynników.

Przykład działał

Biorąc pod uwagę, (4,1)jako para wyjściowej, bierzemy czwarty i pierwszych liczb pierwszych (7,2)i pomnożyć je → 14. To zwielokrotnienie sprawia, że ​​funkcja jest niezależna od kolejności dwóch elementów.

Zaczynamy od 14faktoryzacji (2,7)i zwracamy indeksy 2oraz 7na liście liczb pierwszych → (1,4).

C # , 80 bajtów (38 + 42)

Dane

Enkoder

• Wprowadź Int32 l liczbę A.
• Wprowadź Int32 r liczbę A.
• Wyjście Int64 Oba zespoły zostały połączone

Dekoder

• Wprowadź Int32 v wartość
• Dane wyjściowe Int32[] Tablica z dwoma oryginalnymi liczbami całkowitymi.

Grał w golfa

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

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

Bez golfa

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

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

Nieczytelny czytelny

// 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 };
};

Pełny kod

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 )} ]" );
        }
    }
}

Prasowe

• v1.0 - 80 bytes- Wstępne rozwiązanie.

Notatki

• Żaden

Python: 41 + 45 = 86

enkoder: 41

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

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

(11110111, 11110111)

dekoder: 45

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

d(11110111)

[4, 3]

Starsza próba:

Python: 114: 30 + 84

enkoder: 30

akceptuje 2 liczby całkowite, zwraca ciąg znaków

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

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

(432, 432)

dekoder: 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

dekoder2: 120

kolejna próba ze zrozumieniem generatora i 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