Zaprojektuj przemienną funkcję iniekcyjną między dowolnym (ograniczonym) nieskończonym zestawem i ich nieuporządkowanymi parami

18

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.

HyperNeutrino
źródło
Czy to nie pasuje lepiej do puzzling.stackexchange.com ?
Jakube,
2
@Jakube Niekoniecznie, ponieważ musisz pisać kod.
Pan Xcoder,
Zakładam, że pary są unikalne, ale liczby użyte w tych parach nie są? Kiedy więc 1,2jest jedna z tych par, 1,3może być również potencjalną parą (obie wykorzystują 1)?
Kevin Cruijssen
@KevinCruijssen Nie jestem pewien, co masz na myśli
HyperNeutrino,
@Giuseppe Odwrotność nie musi być w stanie zwrócić prawidłowej kolejności; to tylko, że dla funkcji fi jej odwrotności g, sorted((x, y))powinna być taka sama jaksorted(g(f(x, y)))
HyperNeutrino

Odpowiedzi:

13

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.

Laikoni
źródło
przez OP, wspólny kod musi być policzony dwukrotnie
dumny haskeller 11.09.17
5

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.

Pręt
źródło
niezłe podejście! +1
HyperNeutrino,
4
Nie działa dla wielu liczb takich jak 2i 10na przykład (które są w domenie)
Emigna
Pewnie. Przykład 1 , Przykład 2
Emigna,
Druga funkcja ma działać dla dowolnej wartości w S, a nie tylko dla tej, która została wygenerowana z pierwszą funkcją (popełniłem ten sam błąd).
Arnauld,
4

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!

Erik the Outgolfer
źródło
1
Dlaczego opinie negatywne? To nie jest algorytm Rod.
Erik the Outgolfer,
4

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.

Neil
źródło
4

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!

nwellnhof
źródło
(x+1)->-~x
tsh
3

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).
Dennis
źródło
2
Proszę o wyjaśnienie. Nie jestem pewien, czy to jest ważne ...
Erik the Outgolfer
Dodałem algorytm.
Dennis
Coś mi się nie przylega ... chociaż nie jestem pewien, czy to też jest nieprawidłowe. Zasadniczo nie jest dobrze, że używasz obu ci Œċ... chociaż mogę się mylić. BTW, to była moja odpowiedź, że wygraliście> _>
Erik the Outgolfer
Różnica jest minimalna dla par. Gdyby C oblicza kombinacje bez zamiany, a Ƈ oblicza kombinacje z, nƇ2 = nC2 + n .
Dennis,
2

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.

Kelly Lowder
źródło
2

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.

histocrat
źródło
S = ten zestaw (link OEIS)
Giuseppe,
Dzięki, S jest tak naprawdę podzbiorem tej sekwencji OEIS, ponieważ zawiera tylko liczby, których 1 mają indeksy w S.
histocrat
no tak, oczywiście. Cóż, żadna inna sekwencja nie pasuje do pierwszych kilku terminów (do 32).
Giuseppe,
Dodaj 0 do S i możesz zapisać kilka ubytków.
nwellnhof,
2

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!

Roberto Graham
źródło
1
Możesz zagrać w golfa na kilka części. W funkcji parowania: int i=(""+a[0]).length()może być int i=(f+a[0]).length(); przestrzeń między c=0,j;i>0;można usunąć; a[0].parseIntmoże być new Integer. W funkcji depair: wszystkie trzy r.parseIntmogą być r.decode; i możesz stworzyć zmienną int t.length(), ponieważ używasz jej dwa razy.
Kevin Cruijssen
1

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 .

Erik the Outgolfer
źródło
Twój drugi program może zaoszczędzić 5 bajtów z L2ã € {R'RI <è
Emigna
@Emigna Nice trick with 2ã€{RÙR!
Erik the Outgolfer,
1

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.

tsh
źródło
1

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.

Dave
źródło
0

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

Lew
źródło
Właściwie, patrząc na usuniętą odpowiedź Arnaulda, jej algorytm jest jeszcze lepszy, a przeniesienie jej do Husk dałoby 6 bajtów ... Czy ktoś mógłby potwierdzić, czy jego rozwiązanie (i moje też) jest prawidłowe, czy nie?
Leo
Nie działa dla liczb pierwszych (które są w domenie liczb całkowitych dodatnich)
Emigna
@Emigna druga funkcja nie, ale liczby pierwsze nigdy nie są zwracane przez pierwszą ...
Leo
Twoja domena ma dodatnie liczby całkowite, więc obie metody muszą działać na dodatnie liczby całkowite. EDYCJA: a przynajmniej to było kiedyś wymaganiem. Wydaje się, że obecne reguły zezwalają na podzbiór domeny.
Emigna
0

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
auhmaan
źródło
0

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
Maarten Fabré
źródło
1
na podstawie drugiej próby: e=lambda*x:10**sum(x)-10**min(x);d=lambda z:map(z .count,'09'); TIO
tsh
@tsh bardzo miło.
Dostosuję