Verwandte, aber dies erfordert nur positive ganze Zahlen und muss nicht kommutativ sein

Die Cantor Pairing-Funktion wird in diesem Wikipedia-Artikel beschrieben . Im Wesentlichen handelt es sich um eine Operation, bei der bei Anwendung auf zwei Werte X und Y die ursprünglichen Werte X und Y erhalten werden können, wenn das Ergebnis angegeben wird.

Ihre Aufgabe ist es zwei Funktionen zu entwerfen: eine , die führt X, Y -> Zund die andere , welche führt Z -> X, Y. Hier ist der Haken: X, Y -> ZMuss kommutativ sein. Dies bedeutet, dass Z -> X, Ynicht festgestellt werden kann, ob die Eingabe X, Yoder war Y, X.

Die formale Definition dieser Herausforderung wäre:

Wählen Sie eine abzählbare unendliche Menge S von Zahlen.
Entwerfen Sie zwei Funktionen, die die folgenden Aufgaben ausführen:

• Geben Sie bei einem ungeordneten Wertepaar in S einen Wert in S zurück
• Wenn Sie einen Rückgabewert von der Anfangsfunktion erhalten, geben Sie das ungeordnete Wertepaar zurück, das bei der Übergabe durch die erste Funktion als Eingabe-Ganzzahl ausgewertet wird. Das Verhalten dieser Umkehrfunktion ist mir egal, wenn die Eingabe kein Rückgabewert aus der ersten Funktion ist.

Bedarf

• Das Ergebnis sollte zwischen den Läufen identisch sein.
• {a, a} ist ein ungeordnetes Paar

Hinweis: Ihre Antwort wird mit größerer Wahrscheinlichkeit von mir positiv bewertet, wenn Sie einen Beweis vorlegen. Ich werde die Antworten jedoch testen, wenn ich sie erhalte und positiv bewerten, sobald ich mir ziemlich sicher bin, dass sie funktioniert.

Haskell , 65 + 30 = 95 Bytes

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

Probieren Sie es online!

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

Probieren Sie es online!

Hinweis: Wenn die beiden Funktionen Code gemeinsam nutzen können, sind dies nur 75 Byte:

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

Probieren Sie es online! Die Domäne sind die positiven ganzen Zahlen. Die Funktion (#)führt das Pairing durch, die Funktion (l!!)das Inverse. Anwendungsbeispiel: Beides (#) 5 3und (#) 3 5Ertrag 12und (l!!) 12Ertrag (5,3).

Dies funktioniert, indem alle sortierten Paare explizit in einer unendlichen Liste aufgelistet werden 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), ...`

Die Kodierung ist dann nur der Index in dieser Liste.

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

Probieren Sie es online!

c.HQ\a

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

Probieren Sie es online!
Bereich: Positive ganze Zahlen.

Jelly , 8 + 11 = 19 Bytes

Zurückgesetzt, da Rods Algorithmus nicht funktionierte.

Dies funktioniert im Bereich der positiven ganzen Zahlen.

Nimmt xund yals 2 Argumente, egal in welcher Reihenfolge, zurück z.

»’RSð+ð«

Probieren Sie es online!

Nimmt zund kehrt zurück[min(x, y), max(x, y)]

R€Ẏ,Rx`$ị@€

Probieren Sie es online!

JavaScript (ES7), 44 Byte

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

Ordnet nicht negative ganze Zahlen einer Teilmenge davon zu.

C (gcc) , 36 + 39 = 75 Bytes

Vielen Dank an @tsh für das Speichern von zwei Bytes.

Die Domain besteht aus nicht negativen ganzen Zahlen.

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

Nimmt xund ykehrt zurück z.

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

Nimmt ein intArray mit zwei Elementen an . Das zweite Element muss zvor dem Aufruf auf gesetzt werden. Nach dem Anruf renthält xund y.

Probieren Sie es online!

Jelly , 13 11 Bytes

Paar positive ganze Zahlen bis positive ganze Zahl, 5 Bytes

Ṁc2+Ṃ

Probieren Sie es online!

positive ganze Zahl bis Paar positiver ganzer Zahlen, 6 Bytes

ŒċṀÞị@

Probieren Sie es online!

Algorithmus

Wenn wir die Menge aller ungeordneten Paare positiver Ganzzahlen nach ihrem Maximum und dann nach ihrer Summe sortieren, erhalten wir die folgende Reihenfolge.

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

Die erste Funktion nimmt ein Paar {x, y} und findet ihren Index in dieser Reihenfolge.

Die zweite Funktion nimmt eine positive ganze Zahl z und gibt das z- ^te Element der Sequenz zurück.

Beachten Sie, dass diese Zuordnung mit der in @ EriktheOutgolfers Gelee-Antwort übereinstimmt .

Wie es funktioniert

Ṁ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 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-#})&

Dies ist die einzige bekannte quadratische Paarungsfunktion für Z <-> ZxZ, die mit Min und Max kombiniert wird, um die Ordnung zu verlieren.

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]}

Ich versuche einen Weg zu finden, um geschickt eine unendliche Menge auszuwählen, um dies zu vereinfachen. Dies ist das Beste, was ich bisher habe.

Wir definieren f (x, y) = 2 ^x-1 bitweise oder 2 ^y-1 . Die Domain besteht aus der Menge, die rekursiv als 1,2 definiert ist, und allen Zahlen, die durch Aufrufen von f auf Zahlen in der Menge erzeugt werden können (beachten Sie, dass f (1,1) = 1 und f (2,2) = 2 ist, also 1 und 2 haben Inverse). Die resultierenden Zahlen haben entweder eine oder zwei Einsen in ihrer binären Erweiterung, wobei die Indizes der Einsen den Zahlen in der Menge entsprechen. Wir können das ursprüngliche ungeordnete Paar herausholen, indem wir die Indizes nehmen. Wenn es nur eine 1 gibt, bedeutet dies, dass die Elemente des Paares gleich sind.

Zum Beispiel ist f (3,5) 20, weil 20 in der Basis 2 10100 ist, was 1s an der 3. und 5. Stelle mit der geringsten Signifikanz hat.

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

Pair-Funktion

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

Probieren Sie es online!

Depair-Funktion

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

Probieren Sie es online!

05AB1E , 6 + 11 = 17 Bytes

Port meiner Gelee Antwort.

Bereich: positive ganze Zahlen.

Nimmt eine Liste [x, y]als Eingabe und kehrt zurück z.

{`<LO+

Probieren Sie es online!

Übernimmt eine positive Ganzzahl zals Eingabe und gibt zurück [min(x, y), max(x, y)].

L2ã€{RÙR¹<è

Probieren Sie es online!

-5 danke an Emigna .

JavaScript, 72 Bytes

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

Funktioniert für positive ganze Zahlen (theoretisch). Ganz einfach: Sortiere zwei Zahlen in einer (magischen) Reihenfolge, verbinde sie als Zeichenfolge mit einem Buchstaben "a"und analysiere sie als hexadezimale Ganzzahl.

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 Bytes

Encoding-Funktion, nimmt zwei Eingänge n, m. Ausgangsprodukt aus n-ter und m-ter Primzahl.

,iYq]*

Schritte:

• , - Mach es zweimal
• i - Eingang drücken
• Yq - Popeingang, drücke Eingangstaste
• ]* - Zweimal beenden, beide Primzahlen platzen lassen und Produkt drücken

Dekodierungsfunktion, nimmt eine Eingabe m. Gibt die Anzahl der Primzahlen unter jedem der Primfaktoren von n aus.

iYf"@Zqn

Schritte:

• i - Eingang drücken
• Yf - Pop-Eingabe, Push-Array von Primfaktoren
• " - Für n im Array
• @Zq - Array von Primzahlen unter n schieben
• n - Array öffnen, Länge des Arrays verschieben

Dies ist kommutativ, weil die Multiplikation kommutativ ist, und injektiv, weil Primfaktoren eindeutig sind. Nicht, dass dies nicht auf die ganzen Zahlen zutrifft.

Schale , 5 + 3 = 8 Bytes

Ich hoffe wirklich, dass ich die Herausforderung richtig gelöst habe. Ich sehe einige gelöschte Antworten, die mir als gültig erscheinen ...

Paare positiver Ganzzahlen zu einer einzelnen positiven Ganzzahl:

¤*!İp

Probieren Sie es online!

Es funktioniert, indem die Zahlen bei den gegebenen Indizes (1-indiziert) aus der Liste der Primzahlen genommen und multipliziert werden.

Ergebnis der ersten Funktion für Paare positiver Ganzzahlen:

mṗp

Probieren Sie es online!

Wir faktorisieren die eingegebene Zahl und geben den Index in der Liste der Primzahlen aller (beider) Faktoren zurück.

Gearbeitetes Beispiel

Als Startpaar (4,1)nehmen wir die vierte und erste Primzahl (7,2)und multiplizieren sie → 14. Diese Multiplikation macht die Funktion unabhängig von der Reihenfolge der beiden Elemente.

Ausgehend von 14faktorisieren wir es (2,7)und geben die Indizes von 2und 7in der Liste der Primzahlen zurück → (1,4).

C # , 80 Bytes (38 + 42)

Daten

Encoder

• Geben Sie Int32 l eine Zahl ein
• Geben Sie Int32 r eine Zahl ein
• Ausgang Int64 Beide Ints sind miteinander verschmolzen

Decoder

• Eingabe Int32 v Der Wert
• Ausgabe Int32[] Ein Array mit den beiden ursprünglichen Ints.

Golf gespielt

// 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 lesbar

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

Vollständiger 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- Anfangslösung.

Anmerkungen

• Keiner

Python: 41 + 45 = 86

Geber: 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]

Älterer Versuch:

Python: 114: 30 + 84

Drehgeber: 30

Akzeptiert 2 Ganzzahlen und gibt einen String zurück

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

ein weiterer versuch mit generatorverständnis und summe

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