Encuentra una función con ciclos de cada longitud

11

Se dice que una función tiene un ciclo de longitud n si existe una x en su dominio tal que f n (x) = x y f m (x) ≠ x para 0 <m <n , donde el superíndice n denota n - pliegue la aplicación de f . Tenga en cuenta que un ciclo de longitud 1 es un punto fijo f (x) = x .

Su tarea es implementar una función biyectiva de los enteros a sí mismos, que tiene exactamente un ciclo de cada longitud positiva n . Una función biyectiva es una correspondencia uno a uno, es decir, cada entero asignado exactamente a una vez. Tener exactamente un ciclo de longitud n significa que hay exactamente n números distintos x para los cuales f n (x) = x y f m (x) ≠ x para 0 <m <n .

Aquí hay un ejemplo de cómo se vería tal función alrededor de x = 0 :

x     ... -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7 ...
f(x)  ...  2  4  6 -3 -1  1 -4  0 -2  5  7 -7 -6  3 -5 ...

Este extracto contiene ciclos de longitud 1 a 5 :

n   cycle
1    0
2   -2  1
3   -4 -3 -1
4   -5  6  3  7
5   -7  2  5 -6  4
...

Tenga en cuenta que anteriormente estoy usando "función" solo en el sentido matemático. Puede escribir una función o un programa completo en el idioma que elija, siempre que tome un solo entero (con signo) como entrada y devuelva un solo entero (con signo). Como de costumbre, puede recibir información a través de STDIN, argumento de línea de comando, argumento de función, etc. y salida a través de STDOUT, valor de retorno de función o argumento de función (fuera), etc.

Por supuesto, muchos idiomas no admiten (fácilmente) enteros de precisión arbitraria. Está bien si su implementación solo funciona en el rango del tipo de entero nativo de su idioma, siempre que cubra al menos el rango [-127, 127] y que funcione para enteros arbitrarios si el tipo de entero del idioma se reemplaza por arbitrario- enteros de precisión.

Se aplican reglas estándar de .

Martin Ender
fuente
2
Estrechamente relacionada. Si bien las diferencias parecen menores, implican que ninguno de los enfoques anteriores funciona sin modificaciones significativas, y en particular no creo que el enfoque ganador de ese desafío pueda adaptarse en absoluto.
Martin Ender
"tiene exactamente un ciclo de cada longitud", "tiene muchos ciclos de duración evry": ¿es esta la única diferencia que distingue a este de los demás?
Abr001am
@ Agawa001 Esa es una diferencia, la otra es que el otro desafío se trata de funciones en los enteros positivos, mientras que este desafío solicita una función en todos los enteros.
Martin Ender
1
Creo que su definición de ciclo debe incluir que n es mínima. De lo contrario, su ciclo de longitud 2 también cuenta como su ciclo de longitud 4 y 6 y así sucesivamente.
xnor
@xnor Whoops, buen punto.
Martin Ender

Respuestas:

2

Pyth, 27 18 bytes

_h?gQ0^2Q*.5@,Q-xh

Explicación (Pyth se inicializa Qal entero de entrada):

_                       negative of (
                          (
  ?gQ0                      if Q >= 0:
      ^2Q                     2**Q
                            else:
         *.5                  half of
            @        Q          element Q (modulo list length) in
             ,                    the two element list [
              Q                     Q,
                 hQ                 ((Q plus 1)
                x  Q                 XOR Q)
               -    Q               minus Q
                                  ]
 h                        ) plus 1
                        )

Esto tiene ciclos

(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, - 17, -25, -21, -15, -10)
(5, -33, -49, -41, -29, -19, -12)
(6, -65, -97, -81, -57, −37, −23, −14)
(7, −129, −193, −161, −113, −73, −45, −27, −16)
(8, −257, −385, −321, −225 , −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)

El ciclo de longitud n viene dado por

( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).

Cada número entero k ≥ −1 aparece como el primer elemento del ciclo ( k + 2). Para cada entero k <−1, podemos escribir de forma única 1 - k = 2 ^ i ⋅ (2⋅ j + 1) para algunos i , j ≥ 0; entonces k aparece como el elemento ( j + 2) th del ciclo ( i + j + 2).

Anders Kaseorg
fuente
5

MATL , 47 bytes

E|G0<-QXJ:tQ*2/0hStJ<f0))Q2MQ)&:J6M-)2/ttk>Eq*k

Pruébalo en línea!

Explicación general

La función 2 a continuación es la misma que la utilizada en la respuesta de @ Sp3000 al desafío relacionado. Gracias a @ Agawa001 por notarlo.

La función es la composición de tres:

  1. Biyección de Z (los enteros) a N (los naturales).
  2. Biyección de N a N con la característica deseada (un ciclo de cada longitud).
  3. Inverso de la función 1.

Funciones 1 y 3 se utilizan porque es más fácil (creo) para conseguir el comportamiento deseado en N que en Z .

La función 2 es la siguiente: la línea superior es dominio, la línea inferior es codominio. Las comas se usan para mayor claridad:

1,  2  3,  4  5  6,  7  8  9  10  ...
1,  3  2,  6  4  5, 10  7  8   9  ...

El primer bloque (de arriba 1a abajo 1) es un ciclo de longitud 1. El segundo (de 2 3a 3 2) es un ciclo de longitud 2, etc. En cada bloque, la parte inferior (imagen de la función) es la parte superior desplazada circularmente Un paso a la derecha.

La función 1 es la siguiente:

 -5  -4  -3  -2  -1   0  +1  +2  +3  +4  ...
+10  +8  +6  +4  +2  +1  +3  +5  +7  +9  ...

La función 3 es la misma que 1 con las dos líneas intercambiadas.

Ejemplos

La imagen de 3es -5. Primero 3se asigna a la 7función 1; luego 7se asigna a la 10función 2; luego 10se asigna a -5` por la función 3.

El ciclo de longitud-1 es 0. El ciclo de longitud 2 es -1 1. El ciclo de longitud 3 es -3 2 -2, etc.

Código explicado

Las funciones 1 y 3 son sencillas.

La función 2 funciona al encontrar el punto final inferior del bloque de entrada correspondiente. Por ejemplo, si la entrada a esta función es 9encontrar 7(ver bloques más arriba). Luego selecciona el punto final superior, que está 10en el ejemplo. El desplazamiento circular del bloque se logra gracias a la indexación modular basada en 1 de MATL.

         % FUNCTION 1
         % Implicit input
E|       % Multiply by two. Absolute value
G0<      % 1 if input is negative, 0 otherwise
-        % Subtract
Q        % Add 1
XJ       % Copy to clipboard J. Used as input to the next function

         % FUNCTION 2
:        % Range [1 2 ... J], where J denotes the input to this function
tQ*      % Duplicate, increment by 1, multiply
2/       % Divide by 2
0hS      % Prepend a 0. This is needed in case J is 0
tJ<f     % Duplicate. Find indices that are less than the input J
0)       % Pick the last index.
)        % Apply as index to obtain input value that ends previous block
Q        % Add 1: start of current block
2M       % Push the two arguments to second-to-last function call
Q)       % Add 1 and use as index: end of current block
&:       % Inclusive binary range: generate input block 
J        % Push J (input to function 2)
6M-      % Subtract start of block
)        % Apply as index (1-based, modular). This realizes the shifting

         % FUNCTION 3
2/       % Divide by 2
ttk>     % Duplicate. 1 if decimal part is not 0; 0 otherwise
Eq       % Multiply by 2, add 1
*        % Multiply
k        % Round down
         % Implicit display
Luis Mendo
fuente
este es un giro de la función sp3000 s ¿verdad?
Abr001am
@ Agawa001 ¿Ah sí? No vi el otro desafío. Voy a echar un vistazo
Luis Mendo
Oh. Definitivamente lo es. Al menos eso aclara que mi razonamiento, si no es original, era correcto :-)
Luis Mendo
Es sorprendente cómo más de una mente está enmarcada para exudar ideas cercanas.
Abr001am
4

Python 2, 55 bytes

g=lambda n,k=1:n/k and~g(~n+k*(n>0),k+1)+k*(n>0)or-~n%k

59 bytes:

g=lambda n,k=1:n<0and~g(~n,2)or n/k and k+g(n-k,k+2)or-~n%k

Crea los ciclos.

[0]
[-1, -2]
[1, 2, 3]
[-3, -4, -5, -6]
[4, 5, 6, 7, 8]
...

Modificado de mi solución en el desafío anterior , que se modificó desde la construcción de Sp3000 .

La función

g=lambda n,k=1:n/k and k+g(n-k,k+2)or-~n%k

realiza ciclos de números impares de números no negativos

[0]
[1, 2, 3]
[4, 5, 6, 7, 8]
...

Para encontrar el tamaño de ciclo correcto k, desplace la entrada nhacia abajo k=1,3,5,7,...hasta que el resultado esté en el intervalo [0,k). Ciclo este intervalo con la operación n->(n+1)%k, luego deshacer todas las sustracciones realizadas en la entrada. Esto se implementa de forma recursiva por k+g(n-k,k+2).

Ahora, necesitamos lo negativo para hacer los ciclos pares. Tenga en cuenta que si modificamos gpara empezar k=2en g, nos gustaría llegar ciclos, incluso de tamaño

[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]
...

Estos biject a negativos a través de bits de complemento ~. Entonces, cuando nes negativo, simplemente evaluamos g(n)como ~g(~n,2).

xnor
fuente
No sé si ayuda, pero kparece ser otra forma de calcular Math.floor(Math.sqrt(n))*2+1.
Neil
@Neil Busqué determinar los límites y los tamaños de ciclo aritméticamente e incluso hacer todo el cálculo de esa manera, pero estas expresiones son largas en Python y descubrí que la recursión es más corta.
xnor
3

Python 3, 110 bytes

Todavía no he descubierto cómo poner una lambda allí

si n es un número de triángulo [1,3,6,10,15,21,28, etc ...] entonces f (n) es el orden en la lista multiplicado por uno negativo. Si el número es negativo, dele 1 + el siguiente número de triángulo más pequeño. De lo contrario, incremente.

Ejemplo: 5 no es un número de triángulo, así que suma 1.

Próxima iteración, tenemos 6. 6 es un número de triángulo, y es el tercero en la lista, así que sale -3.

El programa da estas listas

longitud 1: [0]

longitud 2: [1, -1]

longitud 3: [2,3, -2]

longitud 4: [4,5,6, -3]

longitud 5: [7,8,9,10, -4]

x=int(input())
if x<0:print((x**2+x)/2+1)
else:
 a=((8*x+1)**.5-1)/2
 if a%1:print(x+1)
 else:print(-a)

Editar: Gracias de nuevo a @TuukkaX por eliminar el exceso de caracteres.

Magenta
fuente
1
Se podría cambiar 0.5a .5y input('')a input().
Yytsi
2

Python 3, 146 bytes

Para cada número mayor que 0, hay bucles pares (len 2,4,6,8 ...), y menos que 0, bucles impares (1,3,5,7). 0 mapas a 0.

(-3, -2, -1), (0), (1,2), (3,4,5,6)

mapas a

(-2, -1, -3), (0), (2,1), (6,3,4,5)

f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5)
x=int(input());n=f(x)
if x>0:b=n*(n-2)/4
else:b=-((n+1)/2)**2
print(b+1+(x-b-2)%n)

Editar: @TuukkaX despegó 8 bytes de la solución anterior. Y otros 3.

Magenta
fuente
1
Yo creo que se puede eliminar un espacio en blanco antes de la sentencia if en la primera línea. Y mipodría cambiarse a algo más pequeño, como b.
Yytsi
Aquí está el mismo programa de golf:f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Yytsi
1
Gracias, @TuukkaX. Olvidé la variable de 2 caracteres 'mi'.
Magenta
1
También cambié input('')a input(). Las comillas son inútiles ya que no tenemos que imprimir nada en la consola cuando solo queremos obtener la entrada.
Yytsi
1
Incluso más corto. Se eliminaron los ceros antes de los puntos. f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Yytsi
2

Matlab (423)

function u=f(n),if(~n)u=n;else,x=abs(n);y=factor(x);for o=1:nnz(y),e=prod(nchoosek(y,o)',1);a=log(x)./log(e);b=find(a-fix(a)<exp(-9),1);if ~isempty(b),k=e(b);l=fix(a(b));break;end;end,if(abs(n)==1)k=2;l=0;end,if(k==2)l=l+1;x=x*2;end,e=dec2base(l,k)-48;o=xor(e,circshift(e,[0 1]));g=~o(end);if(~o|nnz(o==1)~=numel(e)-g),u=n*k;else,if((-1)^g==sign(n)),u=sign(n)*k^(base2dec([e(2:end-1) 1]+48,k)-(k==2));else,u=n*k;end,end,end
  • No competir porque rompe un buen récord de estar en condiciones para la última clasificación, mientras lucho por acortarlo lo más posible.

  • Algunos errores no sensitivos relacionados con la precisión en matlab que no pude encontrar ninguna salida, excepto hacer mi código sarcásticamente grande, por otro lado, el mapeo que opté fue en términos de factores principales y logaritmo n-ary.

Ejecución

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



 ----------------------------

Explicación

  • Teniendo en cuenta, en primer lugar, que cualquier número puede escribirse como producto de exponentes de primos N=e1^x1*e2^x2...de esta base. Elegí mapear imágenes de ciclos Cque se extraen del mayor exponente del factor más pequeño (no necesariamente primo) de que N es una potencia perfecta de .

  • en palabras más simples, sea N=P^xdonde P es la raíz perfecta más pequeña, xdenota precisamente dos términos esenciales para el ciclo: x=Ʃ(r*P^i)un término Pes la base del ciclo y también una raíz perfecta para el número principal N, y kes el grado del ciclo C=p^k, donde ivaría entre 1 yk, el coeficiente rse incrementa en 1 y se limita por P-1 para cualquier preimagen siguiente hasta que todos los coeficientes se establezcan en r = 1, por lo que nos movemos al inicio de ese ciclo.

  • Para evitar colisiones entre ciclos, la elección de la exponenciación de los primos en lugar de sus productos es precisa, porque como ejemplo de dos ciclos de bases 3y 2un punto de encuentro entre ellos, puede 3*2evitarse ya que un ciclo se define por su grado más que su base, y para el punto de encuentro hay otro ciclo de base 6y grado 1.

  • Los números negativos colocan una excepción, en cuanto a esto, reservé grados impares para números negativos, y grados pares para el resto. Cómo es eso ?

    para cualquier número N incrustado dentro de un ciclo P^k, se escribe como P^(a0*P^i0+a1*P^i1+...), la cantidad (a0*P^i0+a1*P^i1+...)se traduce en base P-aria como a0,a1,...., para aclarar este punto si (p = 2) la secuencia debe estar en base binaria. Como se sabe prealably sin establecer la condición de grados positivos / negativos y la excepción (+/- 1), un número N está en los bordes de un ciclo de grados ksi y solo si la secuencia Ase escribe como 1111..{k+1}..10o 111..{k}..1para todas las bases, de lo contrario no se necesita rotación, por lo tanto, la asignación de una condición negativa / positiva para los respectivos grados pares / impares k/k'para ambos hace una secuencia impar escrita en la forma 101..{k}..100, una secuencia par se escribe en la forma 101..{k'}..10para un borde inicial de un ciclo numérico negativo / positivo respectivamente .

    Ejemplo:

    Tomando un número N=2^10, x=10=2^1+2^3se escribe la secuencia A A=1010, este tipo de secuencia es sintomática de un borde finito del ciclo numérico positivo C=2^3, por lo que la siguiente imagen es la del borde inicial, A=011que es 8, Pero , al estandarizar este resultado a (+ / -) 1 excepción se 2^10/2asigna 8/2y la imagen anterior no debe rotarse.

    Tomando un número N=-3^9, x=9=3^2se escribe la secuencia A A=100, este tipo de secuencia sintomatiza un borde finito del ciclo numérico negativo C=3^1, por lo que la siguiente imagen es la del borde inicial, A=01que es 3, pero, al adaptar este resultado a negativo / positivo -3^9mapas de condición a -3.

  • para la pareja (-/+)1, pensé en introducirlo dentro de un número de bases 2cíclicas, con el pretexto de que una secuencia ordinaria de grupos cíclicos {2,4}{8,16,32,64}..está formada de otra forma {1,2}{4,8,16,32}.., esto evita cualquier pérdida de elementos anteriores, y la operación realizada solo está cambiando con estallidos un nuevo elemento en


Resultados:

ejecutando esta pequeña hoja de códigos para verificar los primeros rangos razonables de números cíclicos:

for (i=1:6) 
index=1;if(max(factor(i))>=5) index=0;end
for ind=0:index
j=f(((-1)^ind)*i); while(((-1)^ind)*i~=j)fprintf('%d ',j);j=f(j);end,fprintf('%d \n',(-1)^ind*i),pause,end,
end

Esto lleva a estos resultados

 2 1 
 -2 -4 -8 -1 
 1 2 
 -4 -8 -1 -2 
 9 27 3 
 -9 -27 -81 -243 -729 -2187 -6561 -19683 -3 
 8 16 32 64 128 256 512 4 
 -8 -1 -2 -4 
 25 125 625 3125 5 
 36 216 1296 7776 46656 6 
 -36 -216 -1296 -7776 -46656 -279936 -1679616 -10077696 -60466176 -362797056 -2.176782e+009 -1.306069e+010 ??? Error using ==> factor at 27

El último es el error de segmentación, pero se ajusta al rango de entero con signo estándar [-127,127].

Abr001am
fuente
Utilicé esta técnica hace un tiempo para definir funciones hash en un viejo programa C mío, ¡funciona bien!
Abr001am
0

JavaScript (ES6), 73 bytes

f=(n,i=0,j=0,k=0,l=1,m=i<0?-i:~i)=>n-i?f(n,m,k++?j:i,k%=l,l+!k):++k-l?m:j

Funciona enumerando la secuencia (0, -1, 1, -2, 2, -3, 3, ...) hasta que encuentra n, contando los ciclos a medida que avanza. icontiene la entrada actual; jcontiene el inicio del ciclo actual, kel índice dentro del ciclo, lla duración del ciclo actual y mla siguiente entrada en la secuencia. Una vez que encontramos n, tomamos jsi estamos al final de un ciclo o msi no.

Neil
fuente