Diseñe una función inyectiva conmutativa entre cualquier conjunto infinito (restringido) y sus pares desordenados

18

Relacionado, pero esto solo requiere enteros positivos y no tiene que ser conmutativo

La función de emparejamiento de Cantor se describe en este artículo de Wikipedia . Esencialmente, es una operación tal que cuando se aplica a dos valores X e Y, uno puede obtener los valores originales X e Y dado el resultado.

Su tarea es diseñar dos funciones: una que realiza X, Y -> Zy otra que realiza Z -> X, Y. Aquí está el truco: X, Y -> Zdebe ser conmutativo. Esto significa que Z -> X, Yno podrá determinar si la entrada fue X, Yo Y, X.

La definición formal de este desafío sería:

Elija un conjunto infinito contable S de números.
Diseñe dos funciones que realicen las siguientes tareas:

  • Dado un par de valores desordenados en S, devuelve un valor en S
  • Dado un valor de retorno de la función inicial, devuelve el par de valores desordenados que se evalúa en el entero de entrada cuando se pasa por la primera función. No me importa el comportamiento de esta función inversa si la entrada no es un valor de retorno de la primera función.

Requisitos

  • El resultado debe ser idéntico entre ejecuciones.
  • {a, a} es un par desordenado

Nota: es más probable que reciba una respuesta positiva de usted si proporciona una prueba, pero probaré las respuestas cuando llegue a ella y la votaré una vez que esté bastante seguro de que funciona.

Hiperneutrino
fuente
¿No encaja esto mejor para puzzling.stackexchange.com ?
Jakube
2
@Jakube No necesariamente, ya que debe escribir código.
Sr. Xcoder
Supongo que los pares son únicos, pero los números utilizados en esos pares no lo son. Entonces, ¿cuándo 1,2es uno de los pares, 1,3también puede ser un par potencial (ambos usan 1)?
Kevin Cruijssen
@KevinCruijssen No estoy seguro de lo que quieres decir
HyperNeutrino
@Giuseppe El inverso no necesita poder devolver el orden correcto; es solo que para la función fy su inverso g, sorted((x, y))debería ser lo mismo quesorted(g(f(x, y)))
HyperNeutrino

Respuestas:

13

Haskell , 65 + 30 = 95 bytes

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

Pruébalo en línea!

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

Pruébalo en línea!


Nota: Cuando las dos funciones pueden compartir código, esto es solo 75 bytes:

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

Pruébalo en línea! El dominio son los enteros positivos. La función (#)realiza el emparejamiento, la función (l!!)es inversa. Ejemplo de uso: Ambos (#) 5 3y (#) 3 5rendimiento 12, y (l!!) 12rendimientos (5,3).

Esto funciona enumerando explícitamente todos los pares ordenados en una lista infinita 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), ...`

La codificación es solo el índice en esta lista.

Laikoni
fuente
por la OP, el código compartido debe ser contado dos veces
haskeller orgullosos
5

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

Pruébalo en línea!

c.HQ\a

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

Pruébalo en línea!
Dominio: enteros positivos.

varilla
fuente
buen enfoque! +1
HyperNeutrino
44
No funciona para muchos números como 2y 10por ejemplo (que están en el dominio)
Emigna
Seguro. Ejemplo 1 , Ejemplo 2
Emigna
Se supone que la segunda función funciona para cualquier valor en S, no solo uno que se generó con la primera función (cometí el mismo error).
Arnauld
4

Gelatina , 8 + 11 = 19 bytes

Retrocedió ya que el algoritmo de Rod no funcionó.

Esto funciona en el dominio de los enteros positivos.

Toma x y ycomo 2 argumentos, no importa en qué orden, regresa z.

»’RSð+ð«

Pruébalo en línea!

Toma z y devuelve[min(x, y), max(x, y)]

R€Ẏ,Rx`$ị@€

Pruébalo en línea!

Erik el Outgolfer
fuente
1
¿Por qué los votos negativos? Este no es el algoritmo de Rod.
Erik the Outgolfer
4

JavaScript (ES7), 44 bytes

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

Mapas de enteros no negativos a un subconjunto de los mismos.

Neil
fuente
4

C (gcc) , 36 + 39 = 75 bytes

Gracias a @tsh por guardar dos bytes.

El dominio es enteros no negativos.

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

Toma xy yvuelve z.

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

Toma una intmatriz de dos elementos . El segundo elemento debe establecerse zantes de la llamada. Después de la llamada rcontiene xy y.

Pruébalo en línea!

nwellnhof
fuente
(x+1)->-~x
tsh
3

Gelatina , 13 11 bytes

par de enteros positivos a entero positivo, 5 bytes

Ṁc2+Ṃ

Pruébalo en línea!

entero positivo a par de enteros positivos, 6 bytes

ŒċṀÞị@

Pruébalo en línea!

Algoritmo

Si clasificamos el conjunto de todos los pares de enteros positivos no ordenados por su máximo y luego por su suma, obtenemos la siguiente secuencia.

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

La primera función toma un par {x, y} y encuentra su índice en esta secuencia.

La segunda función toma un entero positivo z y devuelve el z th elemento de la secuencia.

Tenga en cuenta que esta asignación es la misma que en la respuesta Jelly de @ EriktheOutgolfer .

Cómo funciona

Ṁ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
fuente
2
Explicación por favor. No estoy seguro de que esto sea válido ...
Erik the Outgolfer
He agregado el algoritmo.
Dennis
Algo no me queda bien ... aunque tampoco estoy seguro de si esto no es válido. Básicamente, no se pega bien si usas ambos cy Œċ... aunque puedo estar equivocado. Por cierto, esa fue mi respuesta que superaste> _>
Erik the Outgolfer
La diferencia es mínima para parejas. Si C calcula combinaciones sin reemplazo y Ƈ calcula combinaciones con, nƇ2 = nC2 + n .
Dennis
2

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

Esta es la única función de emparejamiento cuadrático bien conocida para Z <--> ZxZ combinada con Min y Max para hacerla sin orden.

Kelly Lowder
fuente
2

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

Estoy tratando de encontrar una manera de seleccionar astutamente un conjunto infinito para hacer esto más fácil, este es el mejor que tengo hasta ahora.

Definimos f (x, y) = 2 x-1 bit a bit-o 2 y-1 . El dominio consiste en el conjunto definido recursivamente como que contiene 1,2, y todos los números que pueden producirse llamando a f en los números del conjunto (tenga en cuenta que f (1,1) = 1 yf (2,2) = 2, entonces 1 y 2 tienen inversas). Todos los números resultantes tienen uno o dos 1 en su expansión binaria, con los índices de los 1 correspondientes a los números en el conjunto. Podemos obtener el par desordenado original tomando los índices. Si solo hay un 1, eso significa que los elementos del par son iguales.

Por ejemplo, f (3,5) es 20, porque 20 es 10100 en la base 2, que tiene 1s en el 3er y 5to lugares menos significativos.

histocrat
fuente
Gracias, S es en realidad un subconjunto de esa secuencia OEIS embargo, ya que sólo incluye números cuya 1s tener índices en S.
histocrat
ah si, por supuesto. Bueno, ninguna otra secuencia coincide con los primeros términos (hasta 32).
Giuseppe
Agregue 0 a S y puede guardar algunos decrementos.
nwellnhof
2

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

Función de par

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

Pruébalo en línea!

Función de degradación

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

Pruébalo en línea!

Roberto Graham
fuente
1
Puedes jugar al golf algunas partes. En la función par: int i=(""+a[0]).length()puede ser int i=(f+a[0]).length(); el espacio entre c=0,j;i>0;se puede quitar; a[0].parseIntpuede ser new Integer. En la función de pérdida: los tres r.parseIntpueden ser r.decode; y podrías hacer una variable int para t.length(), ya que la usas dos veces.
Kevin Cruijssen
1

05AB1E , 6 + 11 = 17 bytes

Puerto de mi respuesta de gelatina.

Dominio: enteros positivos.

Toma una lista [x, y]como entrada, devuelve z.

{`<LO+

Pruébalo en línea!

Toma un entero positivo zcomo entrada, regresa [min(x, y), max(x, y)].

L2ã€{RÙR¹<è

Pruébalo en línea!

-5 gracias a Emigna .

Erik el Outgolfer
fuente
Su segundo programa puede guardar 5 bytes con L2ã € {RÙRI <è
Emigna
@Emigna Buen truco con 2ã€{RÙR !
Erik the Outgolfer
1

JavaScript, 72 bytes

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

Funciona para enteros positivos (en teoría). Idea bastante simple: ordenar dos números en un orden (mágico), conectarlos como una cadena por una letra "a", analizarlo como un entero hexadecimal.

tsh
fuente
1

MATL, 6 + 8 = 14 bytes

Función de codificación, toma dos entradas n, m. Producto de salidas de nth prime y mth prime.

,iYq]*

Pasos:

  • , - Haz dos veces
  • i - Entrada de empuje
  • Yq - Pop input, push input'th prime
  • ]* - Finalice dos veces, reviente ambos primos y empuje el producto

Función de decodificación, toma una entrada m. Emite el número de primos debajo de cada uno de los factores primos de n.

iYf"@Zqn

Pasos:

  • i - Entrada de empuje
  • Yf - Entrada pop, matriz de factores primos
  • " - Para n en la matriz
  • @Zq - Empujar matriz de primos debajo de n
  • n - Pop array, longitud de empuje de la matriz

Esto es conmutativo porque la multiplicación es conmutativa e inyectiva porque las factorizaciones primas son únicas. No es que esto no esté en los enteros.

Dave
fuente
0

Cáscara , 5 + 3 = 8 bytes

Realmente espero tener el desafío correcto, veo algunas respuestas eliminadas que me parecen válidas ...

Parejas de enteros positivos a un solo entero positivo:

¤*!İp

Pruébalo en línea!

Funciona tomando los números en los índices dados (indexados en 1) de la lista de números primos y multiplicándolos.

Resultado de la primera función para parejas de enteros positivos:

mṗp

Pruébalo en línea!

Factorizamos el número de entrada y devolvemos el índice en la lista de primos de todos (ambos) de sus factores.

Ejemplo trabajado

Dado (4,1)como una pareja inicial, tomamos el cuarto y primer número primo (7,2)y los multiplicamos →14 . Esta multiplicación es lo que hace que la función sea independiente del orden de los dos elementos.

A partir de 14, lo factorizamos (2,7)y devolvemos los índices de 2y 7en la lista de números primos → (1,4).

León
fuente
En realidad, mirando la respuesta eliminada de Arnauld, su algoritmo es aún mejor, y portarlo a Husk daría como resultado 6 bytes ... ¿Podría alguien confirmar si su solución (y la mía también) es válida o no?
Leo
No funciona para números primos (que están en el dominio de los enteros positivos)
Emigna
@Emigna, la segunda función no lo hace, pero la primera nunca devuelve primos ...
Leo
Su dominio son enteros positivos, por lo que ambos métodos deben funcionar para enteros positivos. EDITAR: o al menos eso solía ser un requisito. Las reglas actuales parecen permitir un subconjunto del dominio.
Emigna
0

C # , 80 bytes (38 + 42)


Datos

Codificador

  • Ingrese Int32 l un número
  • Ingrese Int32 r un número
  • Salida Int64 Ambas entradas fusionadas

Descifrador

  • Ingrese Int32 v el valor
  • Salida Int32[] Una matriz con las dos entradas originales.

Golfed

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

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

Sin golf

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

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

Legible sin golf

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

Código completo

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

Lanzamientos

  • v1.0 - 80 bytes- Solución inicial.

Notas

  • Ninguna
auhmaan
fuente
0

Python: 41 + 45 = 86

codificador: 41

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

(11110111, 11110111)

decodificador: 45

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

[4, 3]

Intento anterior:

Python: 114: 30 + 84

codificador: 30

acepta 2 enteros, devuelve una cadena

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

(432, 432)

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

decodificador2: 120

otro intento con comprensiones de generador y suma

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é
fuente
1
basado en el segundo intento: e=lambda*x:10**sum(x)-10**min(x);d=lambda z:map(z .count,'09'); TIO
tsh
@tsh muy agradable. Lo adaptaré más tarde, o puede enviar su propia respuesta
Maarten Fabré