Genera un par de enteros a partir de uno no negativo

25

Debería escribir un programa o función que tome un entero no negativo Ncomo entrada y salida o devuelva dos enteros (negativo, cero o positivo) Xy Y.

Los enteros se entienden en sentido matemático ya que hay infinitos de ellos.

La función implementada tiene que ser biyectiva . Esto significa que para cada Nuno tiene que generar un X Ypar diferente y cada X Ypar debe emitirse para alguna entrada, Nes decir, todos los siguientes pares deben emitirse para algunos N:

                 ...
    ┌─────┬─────┬────┬────┬────┐
    │-2 -2│-2 -1│-2 0│-2 1│-2 2│
    ├─────┼─────┼────┼────┼────┤
    │-1 -2│-1 -1│-1 0│-1 1│-1 2│
    ├─────┼─────┼────┼────┼────┤
... │0 -2 │0 -1 │0 0 │0 1 │0 2 │ ...
    ├─────┼─────┼────┼────┼────┤
    │1 -2 │1 -1 │1 0 │1 1 │1 2 │
    ├─────┼─────┼────┼────┼────┤
    │2 -2 │2 -1 │2 0 │2 1 │2 2 │
    └─────┴─────┴────┴────┴────┘
                 ...

Tenga en cuenta que U Vy V Uson diferentes pares si U!=V.

Detalles

  • Si su idioma no admite enteros arbitrariamente grandes, está bien, pero su algoritmo debería funcionar con un tipo de datos entero arbitrariamente grande. Su código aún debe admitir valores de entrada al menos 2^31-1.
  • Si elige imprimir o devolver la salida como cadena, no se permiten signos 0ni +signos iniciales. De lo contrario, la representación entera estándar de su idioma está bien.

Ejemplo

Si la tarea fuera hacer una función biyectiva tomando un número entero no negativo Ny generando un número entero, Xuna solución podría ser la función

if (input mod 2 == 0) return N/2 else return -(N+1)/2,

implementado en algún idioma. Esta función devuelve X = 0 -1 1 -2 2...para N = 0 1 2 3 4....

randomra
fuente
¿Se puede repetir cualquiera de los enteros en la salida para una entrada diferente? Por ejemplo, ¿no 10=>11 12, 9=>10 11es válido porque se repite 11?
BrainSteel
1
En cuanto a "biyectivo" se define "11 12" no es lo mismo que "10 11" y, por lo tanto, es válido. Esto se debe a que una función biyectiva se define como una función "donde cada elemento de un conjunto está emparejado con exactamente un elemento del otro conjunto, y cada elemento del otro conjunto está emparejado con exactamente un elemento del primer conjunto. No hay elementos no emparejados "( en.wikipedia.org/wiki/Bijection ). Si invirtiera su función, "11 12" debería generar 10 y "10 11" debería generar 9.
GiantTree
@BrainSteel Su ejemplo es válido. Solo los pares (ordenados) no se pueden repetir. GiantTree es correcto. Se agregó alguna explicación más a la pregunta.
randomra
¿Tiene que ser una biyección dentro del rango entero del idioma dado o debería funcionar para todos los enteros?
flawr
1
@LegionMammal tenía una buena descripción matemática de la tarea: "Debe definir una función biyectiva $ f: N + → Z ^ 2 $. - LegionMammal978". que creo que sería beneficioso en algún lugar de la declaración
Brian J

Respuestas:

15

Pyth, 15

u,-HyeGhGjQ2,ZZ

Pruébalo en línea.

u             reduce
                lambda G,H:    [implicit]
  ,-HyeGhG         (H-2*G[-1],G[0])
  jQ2           base(input(),2)
  ,ZZ           (0,0)
              print result     [implicit]

Una traducción de Python:

g=lambda Z,n:(n-2*Z[1],Z[0])
print reduce(g,binlist(input()),(0,0))

o iterativamente:

(x,y)=(0,0)
for b in binlist(input()):
    (x,y)=(b-2*y,x)
print (x,y)

donde binlistconvierte un número a una lista de dígitos como binlist(4) = [1,0,0].

¿Entonces, cómo funciona esto? Interpreta los dígitos binarios del número como dos números intercalados en dos negativos base como en mi solución Python .norte

El número binario corresponde al par ( x , y ) = ( b 0 - 2 b 2 + 4 b 4 - 8 b 6 + , b 1 - 2 b 3 + 4 b 5 - 8 b 7 + )

norte=...si5 5si4 4si3si2si1si0 0
(X,y)=(si0 0-2si2+4 4si4 4-8si6 6+,si1-2si3+4 4si5 5-8si7 7+).

Si aún no hubiéramos procesado el último dígito de n , tendríamos todos los índices más altos en $ 1 $, n = b 5 b 4 b 3 b 2 b 1 correspondientes al par ( x , y ) = ( b 1 - 2 b 3 + 4 b 5 - 8 b 7 + , b 2 - 2 b 4si0 0norte

norte=...si5 5si4 4si3si2si1
(X,y)=(si1-2si3+4 4si5 5-8si7 7+,si2-2si4 4+4 4si6 6-8si8+).

Entonces podemos expresar los nuevos valores una vez que se lee en términos de los valores anterioressi0 0

(X,y)=(si0 0-2y,X).

(X,y)(si-2y,X)sinorte(X,y)

xnor
fuente
Tenga en cuenta que el soporte MathJax ha sido deshabilitado. Es posible que desee considerar editar su explicación para facilitar la lectura.
Alex A.
32

CJam, 24 22 21 bytes

Mi cerebro tiene problemas para entender las matemáticas que usan otras soluciones. Pero mi cerebro definitivamente entiende binario, ¡así que aquí hay una idea basada en la manipulación de bits!

li4b2fmd2/z{)(\2b^}%p

Pruébalo en línea.

Explicación

Este enfoque trata la entrada como dos valores binarios intercalados, uno para cada número de salida. Todos, excepto el bit menos significativo de cada uno, codifican una magnitud, y el bit menos significativo indica si tomar o no el complemento en bits de esta magnitud. En esta implementación, los bits de posición impar corresponden al primer número de salida (y los bits de posición par corresponden al segundo) y un LSB de 0señales para tomar el complemento.

Por ejemplo, dada una entrada de 73, desintercalar su representación binaria de 1001001bproduce 0 1|0(bits de posición impar) y 1 0 0|1(bits de posición par). El primer valor tiene una magnitud de 01b = 1y debe complementarse para un valor final de ~1 = -2, y el segundo valor tiene una magnitud de 100b = 4y no debe complementarse.

Demostración informal de corrección

Hice un programa de prueba que coloca cada entrada de cero a un número especificado por el usuario menos uno en su ubicación de salida en una cuadrícula 2D. Puedes probarlo en línea también. Aquí hay una salida de este programa que muestra cómo se asigna el algoritmo 0-99:

      -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8

-8                      92 84 86 94                     
-7                      88 80 82 90                     
-6                      76 68 70 78                     
-5                   96 72 64 66 74 98                  
-4                60 52 28 20 22 30 54 62               
-3                56 48 24 16 18 26 50 58               
-2                44 36 12  4  6 14 38 46               
-1                40 32  8  0  2 10 34 42               
 0                41 33  9  1  3 11 35 43               
 1                45 37 13  5  7 15 39 47               
 2                57 49 25 17 19 27 51 59               
 3                61 53 29 21 23 31 55 63               
 4                   97 73 65 67 75 99                  
 5                      77 69 71 79                     
 6                      89 81 83 91                     
 7                      93 85 87 95                     
 8                                                      

El patrón de relleno se ve un poco extraño, ¡pero de hecho es biyectivo! Con cada poder sucesivo de 4, llena un cuadrado con el doble de la longitud del lado anterior. Por ejemplo, así es como se asigna el algoritmo 0-15:

      -2 -1  0  1  2

-2    12  4  6 14   
-1     8  0  2 10   
 0     9  1  3 11   
 1    13  5  7 15   
 2                  

Esto constituye el cuadrado de 4x4 en el medio del cuadrado de 8x8 de 0-63:

      -4 -3 -2 -1  0  1  2  3  4

-4    60 52 28 20 22 30 54 62   
-3    56 48 24 16 18 26 50 58   
-2    44 36 12  4  6 14 38 46   
-1    40 32  8  0  2 10 34 42   
 0    41 33  9  1  3 11 35 43   
 1    45 37 13  5  7 15 39 47   
 2    57 49 25 17 19 27 51 59   
 3    61 53 29 21 23 31 55 63   
 4                              

Lo que constituye el cuadrado de 8x8 en el medio del cuadrado de 16x16 de 0-255:

         -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7   8

 -8     252 244 220 212 124 116  92  84  86  94 118 126 214 222 246 254    
 -7     248 240 216 208 120 112  88  80  82  90 114 122 210 218 242 250    
 -6     236 228 204 196 108 100  76  68  70  78 102 110 198 206 230 238    
 -5     232 224 200 192 104  96  72  64  66  74  98 106 194 202 226 234    
 -4     188 180 156 148  60  52  28  20  22  30  54  62 150 158 182 190    
 -3     184 176 152 144  56  48  24  16  18  26  50  58 146 154 178 186    
 -2     172 164 140 132  44  36  12   4   6  14  38  46 134 142 166 174    
 -1     168 160 136 128  40  32   8   0   2  10  34  42 130 138 162 170    
  0     169 161 137 129  41  33   9   1   3  11  35  43 131 139 163 171    
  1     173 165 141 133  45  37  13   5   7  15  39  47 135 143 167 175    
  2     185 177 153 145  57  49  25  17  19  27  51  59 147 155 179 187    
  3     189 181 157 149  61  53  29  21  23  31  55  63 151 159 183 191    
  4     233 225 201 193 105  97  73  65  67  75  99 107 195 203 227 235    
  5     237 229 205 197 109 101  77  69  71  79 103 111 199 207 231 239    
  6     249 241 217 209 121 113  89  81  83  91 115 123 211 219 243 251    
  7     253 245 221 213 125 117  93  85  87  95 119 127 215 223 247 255    
  8                                                                        
Runer112
fuente
3
¡Muy inteligente! Puede guardar dos bytes utilizando en li4b2fmd2/lugar de 0li2b+W%2/W%. Esto da los mismos enteros, pero en orden inverso.
Dennis
@ Dennis Eso también es muy inteligente. He actualizado la respuesta para usar ese truco. ¡Gracias!
Runer112
12

Pitón 2, 49

Editar: Mejorado a 49 al usar una mejor recursión de un paso para la base -2.

def f(n):x,y=n and f(n/2)or(0,0);return n%2-2*y,x

Aquí hay una versión de Pyth usando reduce.

Editar: Mejorado a 52 cambiando a base -2 desde ternario equilibrado .

Pitón 2, 52

h=lambda n:n and n%2-2*h(n/4)
lambda n:(h(n),h(n/2))

Pitón 2, 54

h=lambda n:n and-~n%3-1+3*h(n/9)
lambda n:(h(n),h(n/3))

Utiliza intercalado de dígitos como la solución Runer112 , pero con binario ternario equilibrado en lugar de binario con signo. Python no tiene una conversión base integrada, por lo que el código la implementa de forma recursiva.

La función auxiliar h(con 3en lugar de 9) toma un número natural y lo convierte de ternario a ternario equilibrado con las sustituciones de dígitos

0 -> 0 
1 -> +1
2 -> -1

Entonces, por ejemplo, 19, que es 201 en base, se convierte en (-1) (0) (+ 1) en ternario balanceado, que es (-1) * 3 ^ 2 + (0) * 3 ^ 1 + (+ 1) * 3 ^ 0 = -8.

El ternario equilibrado es suficiente para codificar cada número entero y, por lo tanto, proporciona una asignación de números naturales a números enteros.

Para mapear a pares de enteros, entrelazamos los dígitos n. Para hacerlo, tenemos que hmirar cada dos dígitos haciendo n/9como el paso recursivo en lugar de hacerlo n/3. Luego, para una coordenada, cambiamos ndividiendo el piso por 3.

Aquí están las primeras 81 salidas, que cubren la región [-4,4] ^ 2.

0 (0, 0)
1 (1, 0)
2 (-1, 0)
3 (0, 1)
4 (1, 1)
5 (-1, 1)
6 (0, -1)
7 (1, -1)
8 (-1, -1)
9 (3, 0)
10 (4, 0)
11 (2, 0)
12 (3, 1)
13 (4, 1)
14 (2, 1)
15 (3, -1)
16 (4, -1)
17 (2, -1)
18 (-3, 0)
19 (-2, 0)
20 (-4, 0)
21 (-3, 1)
22 (-2, 1)
23 (-4, 1)
24 (-3, -1)
25 (-2, -1)
26 (-4, -1)
27 (0, 3)
28 (1, 3)
29 (-1, 3)
30 (0, 4)
31 (1, 4)
32 (-1, 4)
33 (0, 2)
34 (1, 2)
35 (-1, 2)
36 (3, 3)
37 (4, 3)
38 (2, 3)
39 (3, 4)
40 (4, 4)
41 (2, 4)
42 (3, 2)
43 (4, 2)
44 (2, 2)
45 (-3, 3)
46 (-2, 3)
47 (-4, 3)
48 (-3, 4)
49 (-2, 4)
50 (-4, 4)
51 (-3, 2)
52 (-2, 2)
53 (-4, 2)
54 (0, -3)
55 (1, -3)
56 (-1, -3)
57 (0, -2)
58 (1, -2)
59 (-1, -2)
60 (0, -4)
61 (1, -4)
62 (-1, -4)
63 (3, -3)
64 (4, -3)
65 (2, -3)
66 (3, -2)
67 (4, -2)
68 (2, -2)
69 (3, -4)
70 (4, -4)
71 (2, -4)
72 (-3, -3)
73 (-2, -3)
74 (-4, -3)
75 (-3, -2)
76 (-2, -2)
77 (-4, -2)
78 (-3, -4)
79 (-2, -4)
80 (-4, -4)

Una codificación alternativa con un cuarto de imaginario resultó más larga, aunque es muy bonita.

Pitón 2, 63

h=lambda n:n and n%4+2j*h(n/4)
lambda n:(h(n).real,h(n).imag/2)

En un lenguaje con un manejo menos complejo de conversión compleja, este sería probablemente un mejor enfoque. Si pudiéramos generar números complejos, podríamos hacer:

Pitón 2, 38

f=lambda n:n and n%2+n/2%2*1j-2*f(n/4)
xnor
fuente
1
Su función base -2 original haría una respuesta Pyth media. L&b-%b2*2y/b4,yQy/Q2tiene solo 20 bytes de longitud.
Dennis
44
@ Dennis Acabo de escribir una solución Pyth de 15 caracteres.
xnor
Equilibrado ternario y cuarto imaginario. Dos de mis bases favoritas. Seguido solo por Base-e.
Brian Minton
11

Python 2, 98 bytes

Comencemos con un enfoque simple:

def f(N):
 x=a=0;b=2
 while N:x+=1j**b;b+=a<1;a=a or b/2;N-=1;a-=1
 return int(x.real),int(x.imag)

Simplemente forma Nunidades espirales rectangulares de largo en una cuadrícula 2D, comenzando desde el origen, y devuelve las coordenadas del último punto.

La función es biyectiva ya que:

  • Cada punto puede cubrirse, dada una espiral lo suficientemente larga
  • Cada punto solo será cruzado por la espiral una vez

La espiral se ve más o menos así (excepto a partir de 0 en lugar de 1):

Espiral Ulam

grc
fuente
@AlexA. 0**0 == 1en python, así que es lo mismo queif a == 0: a = b/2
grc
Genial, gracias por explicarlo.
Alex A.
@AlexA. Resulta que a=a or b/2es más corto
grc
@grc 0^0=1en todas las matemáticas, no solo en Python.
Daenyth
1
@Daenyth 0**0es en realidad forma indeterminada en matemáticas
Sp3000
8

dc, 49

[1+2~2*1-*n]sm?dsa8*1+v1-2/dd1+*2/lar-dlmx32P-lmx

Esto comienza organizando los enteros no negativos en una cuadrícula de esta manera:

..| 
4 | 14
3 |  9 13
2 |  5  8 12
1 |  2  4  7 11
0 |  0  1  3  6 10
Y +-----------------
  X  0  1  2  3  4 ...

Tenga en cuenta que las posiciones de la cuadrícula se llenan diagonalmente con N creciente. Observe que la línea Y = 0 contiene la secuencia de números triangulares, dada por N = X(X+1)/2. Esta es una ecuación cuadrática que se resuelve usando la fórmula normal, usando solo la raíz + ve, para que podamos determinar X a partir de N cuando Y = 0. Lo siguiente es una combinación aritmética simple para dar {X, Y} único por cada N.

Esto proporciona la calidad biyectiva requerida, pero X e Y no son solo negativos, pero la pregunta requiere todos los enteros posibles. Entonces X e Y se asignan usando ((t+1)/2)*((t+1)~2*2-1)para dar todos los enteros posibles.

dctiene números de precisión arbitrarios, por lo que el rango de entrada a 2^31-1no es un problema. Tenga en cuenta también que la precisión predeterminada es 0 dígitos decimales, y el sqrt()y /redondee hacia abajo que es el comportamiento necesita aquí.

Salida:

$ for i in {0..10}; do dc biject.dc <<< $i; echo; done
0 0
0 -1
-1 0
0 1
-1 -1
1 0
0 -2
-1 1
1 -1
-2 0
0 2
$
Trauma digital
fuente
5

Matlab, 54 bytes

n=input('')+1;[i,j]=find(spiral(2*n)==n);disp([i,j]-n)

La clave aquí es que spiralesto crea una matriz espiral de un tamaño arbitrario.

spiral(3)

devoluciones

ans =

 7     8     9
 6     1     2
 5     4     3

spiral4 4norte2norte104 4norte105 52.91011norte=232

falla
fuente
2

Haskell, 78 74 bytes

(concat[[(x,i-x),(x,x-1-i),(-1-x,x-1-i),(-1-x,i-x)]|i<-[0..],x<-[0..i]]!!)

Prueba de funcionamiento:

*Main> mapM_ (print . (concat[[(x,i-x),(x,x-1-i),(-1-x,x-1-i),(-1-x,i-x)]|i<-[0..],x<-[0..i]]!!) ) [0..20]
(0,0)
(0,-1)
(-1,-1)
(-1,0)
(0,1)
(0,-2)
(-1,-2)
(-1,1)
(1,0)
(1,-1)
(-2,-1)
(-2,0)
(0,2)
(0,-3)
(-1,-3)
(-1,2)
(1,1)
(1,-2)
(-2,-2)
(-2,1)
(2,0)

Cómo funciona: enumere todos los pares en el primer cuadrante en el siguiente orden

  |
 2| #4
  |
 1| #2  #5
  | 
 0| #1  #3  #6
  +---------------
     0   1   2   3 

refleje cada punto en los otros cuadrantes para hacer una lista de 4 listas de elementos. Concatenar todo en una sola lista y tomar el nelemento th.

Editar: la función no necesita un nombre, ordenó las matemáticas. expresiones

nimi
fuente
Puede guardar 4 bytes usando do-notation: ¡ Pruébelo en línea!
ბიმო
1

Haskell , 50 bytes

(0!).succ
l!n=(last$(!).succ:[(,)|odd n])l$div n 2

¡Pruébelo en línea o pruébelo con su inverso!

Sin golf

ntoN2 n = 0 ! (n + 1)

xCounter ! remainingNum
  | odd remainingNum = (xCounter, div remainingNum 2)
  | otherwise        = (xCounter + 1) ! div remainingNum 2

Explicación

(X,y)norte22X(2y+1)-1norte(!)XlxCountery

Tenga en cuenta que la función real f( ntoN2) incrementa la entrada antes de comenzar con el procedimiento.

ბიმო
fuente
1

05AB1E , 35 bytes

>©DÝʒo®sÖ}àsÅÉʒ®sÖ}à<2÷‚εDÈi2÷ë>2÷(

Pruébalo en línea! o como conjunto de pruebas

Explicación

Considerar

F:nortenorte×nortenorte(X,y),
dónde X es el mayor número para que 2X divide norte+1, y donde 2y+1 es el número impar más grande que divide norte+1. El inverso deF es la biyección conocida F-1(X,y)=2X(2y+1)-1.

Entonces considera

sol:norte×norteZ×Z(metro,norte)(h(metro),h(norte)),
dónde
h:norteZnorte{norte2,norte incluso-norte+12,norte impar.
Ya que F, sol y h todos son biyecciones, la composición solF:norteZ×Z Es una biyección.

El programa simplemente calcula solF.

>©DÝʒo®sÖ}àsÅÉʒ®sÖ}à<2÷‚εDÈi2÷ë>2÷( # Full program

                                    # Implicit input: Integer n
>©                                  # Compute n+1 and save it to the register
  DÝ                                # Duplicate n+1 and push the list [0,...,n+1]
    ʒo®sÖ}                          # Only keep those numbers x so that 2^x divides n+1
          à                         # Get maximum element in the list.
           sÅÉ                      # Swap so that n+1 is on top and push [1,3,5,...,n+1]
              ʒ®sÖ}                 # Only keep those numbers z which divides n+1
                   à<2÷             # Compute y = (z-1)/2
                       ‚            # Push the pair [x,y]
                        ε           # Apply the function h to x (and y):
                           i        # if...
                         DÈ         # x is even
                            2÷      # then compute x/2
                              ë>2÷( # else compute -(x+1)/2
                                    # Implicit output: [h(x),h(y)]
Wisław
fuente
wow, votaron por la buena explicación. pero seguramente 05AB1E debería ser capaz de vencer a Pyth?
Solo para ASCII el
Gracias :) Sin duda se puede mejorar, pero probablemente tendrá que usar otro enfoque en lugar de computar solF. Probablemente pueda jugar un poco más bajo, pero sospecho que no mucho
Wisław
0

Mathematica, 46

SortBy[Tuples[Range[2#]-#,2],Norm][[#]]&[#+1]&

Ordene los vectores según su norma, luego tome el nth.

alephalpha
fuente
0

JavaScript, 166168 bytes / caracteres

Nuevo enfoque usando una espiral rectangular como otros están usando.

function f(n){return b=Math,k=b.ceil((b.sqrt(n)-1)/2),t=2*k+1,m=b.pow(t,2),t+=4,m-t>n?(m-=t,m-t>n?(m-=t,m-t>n?[k,k-(m-n-t)]:[-k+(m-n),k]):[-k,-k+(m-n)]):[k-(m-n),-k]}

He utilizado esta respuesta en Math.SE, traduje a JS y comprimido usando UglifyJS .

Este enfoque no utiliza ningún bucle ni crea la espiral de ninguna manera.

Debido a que las coordenadas de la espiral cubren todos los enteros, la función es biyectiva en el sentido de F:norte0 0Z2.

Actualización: Guardado 2 caracteres mediante el almacenamiento Mathen b.

Actualización 2: reemplazado t-=1por t+=4para solucionar el problema que causóF(0 0)=F(8). Esto ya no genera una espiral, pero funciona para todos los enteros no negativosnorte0 0 (todos los números naturales incluidos 0 0)

Árbol Gigante
fuente
1) Volver a publicar exactamente la misma pregunta realmente no ayudará. 2) Copiar otra respuesta y luego usar un minificador para jugar golf tampoco lo hará :)
Optimizer
Al menos sigue todas las reglas establecidas en la pregunta y es un enfoque diferente. Además, no estoy robando el trabajo de otro, pero me refiero a cómo hice esta respuesta.
GiantTree
@Optimizer: 1) Sugerí que GiantTree debería volver a publicar ya que recibió 3 votos negativos (que lo merecían) por su enfoque original e inválido. 2) El código que tomó de Math.SE ni siquiera es JavaScript, por lo que hizo más que simplemente copiarlo en un minificador.
Dennis
@La gente de Dennis puede retractarse de su voto negativo, ya sabes. Además, el uso de un minificador para minificar el código no es realmente recomendable.
Optimizador
@Optimizer Traté de jugar el código, pero usar un compresor me dio un mejor resultado (menos caracteres), así que usé ese en su lugar.
GiantTree