Los números de subfactorial o rencontres ( A000166 ) son una secuencia de números similares a los números factoriales que se muestran en la combinatoria de permutaciones. En particular, el n º subfactorial n indica el número de alteraciones de un conjunto de n elementos. Un trastorno es una permutación en la que ningún elemento permanece en la misma posición. El subfactorial se puede definir mediante la siguiente relación de recurrencia:
!n = (n-1) (!(n-1) + !(n-2))
De hecho, la misma relación de recurrencia es válida para el factorial, pero para el subfactorial partimos de:
!0 = 1
!1 = 0
(Para el factorial tendríamos, por supuesto, 1! = 1. )
Su tarea es calcular ! N , dado n .
Reglas
Al igual que el factorial, el subfactorial crece muy rápidamente. Está bien si su programa solo puede manejar entradas n de modo que ! N pueda ser representado por el tipo de número nativo de su idioma. Sin embargo, su algoritmo debe en teoría funcionar para n arbitraria . Eso significa que puede suponer que los resultados integrales y el valor intermedio pueden ser representados exactamente por su idioma. Tenga en cuenta que esto excluye la constante e si se almacena o calcula con precisión finita.
El resultado debe ser un número entero exacto (en particular, no se puede aproximar el resultado con notación científica).
Puede escribir un programa o una función y utilizar cualquiera de los métodos estándar para recibir entradas y proporcionar salidas.
Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.
Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .
Casos de prueba
n !n
0 1
1 0
2 1
3 2
4 9
5 44
6 265
10 1334961
12 176214841
13 2290792932
14 32071101049
20 895014631192902121
21 18795307255050944540
100 34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601
fuente
Respuestas:
Funciton , 336 bytes
El recuento de bytes supone la codificación UTF-16 con BOM.
Esto define una función
f
que toma un entero y genera otro entero en un giro de 90 grados a la izquierda. Funciona para entradas arbitrariamente grandes.Pruébalo en línea!
Teniendo en cuenta que esto es Funciton, incluso es razonablemente rápido (n = 20 tarda unos 14 segundos en TIO). La desaceleración principal proviene de la doble recursión, ya que no creo que el intérprete Funciton memorice automáticamente las funciones.
Desafortunadamente, algunas fuentes monoespaciadas no monospace correctamente
♭
y / o insertar pequeños espacios entre las líneas. Aquí hay una captura de pantalla del código de TIO en toda su belleza:Creo que podría ser posible jugar al golf un poco más, por ejemplo, cambiando la condición de
>0
a<1
e intercambiando las ramas del condicional, para poder reutilizar el número literal, o tal vez usando una fórmula completamente diferente, pero estoy bastante contento con lo compacto que ya es.Explicación
Básicamente, esto implementa la recursividad dada en el desafío, ¡aunque utiliza el caso base ! (- 1) =! 0 = 1 . n-1 y n-2 se calculan con la función predecesora
♭
, y el resultado intermedio n-1 se reutiliza en tres lugares. No hay mucho más, así que pasaré rápidamente por el flujo de control:Este es el encabezado de la función que emite de entrada de la función de n largo de la línea adjunta. Esto alcanza inmediatamente la unión en T, que simplemente duplica el valor.
El
0
cuadro es solo un literal numérico. Una unión de 4 vías calcula dos funciones: la ruta que conduce desde la parte inferior calcula 0 <n , que usaremos para determinar el caso base. La ruta que va a la izquierda por separado calcula 0 << n (un desplazamiento a la izquierda), pero descartamos este valor con la construcción de Starkov .Llevamos esto al condicional de tres vías
?
. Si el valor es falso, devolvemos el resultado constante1
. El extremo suelto de la derecha?
es la salida de la función. Lo estoy girando 180 grados aquí, para que la orientación relativa de entrada y salidaf
sea más conveniente en el resto del programa.Si la condición era verdadera, se utilizará el otro valor. Veamos el camino que conduce a esta rama. (Tenga en cuenta que la evaluación de Funciton es realmente perezosa, por lo que esta rama nunca se evaluará si no es necesaria, lo que hace posible la recursión en primer lugar).
En la otra rama, primero calculamos n-1 y luego dividimos la ruta dos veces para obtener tres copias del valor (una para el coeficiente de recurrencia, una para el primer subfactorial, la última para n-2 ).
Como dije, decrementamos una copia nuevamente con otra
♭
, luego alimentamos tanto n-1 como n-2 recursivamentef
y finalmente agregamos los dos resultados juntos en el+
.Todo lo que queda es multiplicar n-1 por ! (N-1) +! (N-2) .
fuente
Oasis , 5 bytes
Utiliza la fórmula dada por Martin. Código:
Versión disecada:
con
a(0) = 1
ya(1) = 0
.Explicación,
a(n) =
:Pruébalo en línea!
fuente
X
:-) Por cierto, ¿implementaste esto todavía? Uno de estos días no podremos escapar simplemente cambiando los valores inicialesHaskell , 25 bytes
Pruébalo en línea! Utiliza la otra recurrencia de la página OEIS .
fuente
Jalea , 7 bytes
Este enfoque construye los trastornos, por lo que es bastante lento.
Pruébalo en línea!
Cómo funciona
fuente
Brachylog (2), 11 bytes
Pruébalo en línea!
Explicación
Esto es básicamente una traducción directa de la especificación del inglés al Brachylog (y, por lo tanto, tiene la ventaja de que podría modificarse fácilmente para manejar pequeños cambios en la especificación, como encontrar el número de alteraciones de una lista específica).
fuente
Idiomas con soluciones integradas
Siguiendo la sugerencia de xnor, esta es una respuesta de CW en la que se deben editar las soluciones triviales basadas en un único incorporado para calcular el subfactorial o generar todos los trastornos.
Mathematica, 12 bytes
fuente
Python 3 ,
3532 bytesEsto utiliza la relación de recurrencia ! N = n! (N-1) + (-1) n de la respuesta de Haskell de @ Laikoni , con el caso base ! 0 = 1 .
Pruébalo en línea!
fuente
f=lambda n:n<1or n*f(n-1)+(-1)**n
.n=-1
, no importa en absoluto el valor que utilice. Eso podría ser útil para algunos idiomas (por ejemplo, en Mathematica podría dejarlo sin definir si eso guardara bytes).M , 9 bytes
Como puede ver al eliminar
Ḟ
, M utiliza matemática simbólica, por lo que no habrá problemas de precisión.Pruébalo en línea! No es la solución más corta que se ha publicado, pero es rápida .
Cómo funciona
fuente
MATL ,
98 bytesDe manera similar a la respuesta de @Dennis 'Jelly , esto realmente construye las permutaciones y cuenta cuántos de ellos son trastornos; entonces es lento.
Pruébalo en línea!
fuente
Matemáticas , 21 bytes
Soy muy nuevo en esto y no tengo idea de lo que estoy haciendo ...
Pruébalo en línea!
fuente
Round[(#/. 0->2)!/E]&
y±0=1;±n_:=Round[n!/E]
(aunque no sé si Mathics admite codificaciones de un solo byte para archivos fuente como lo hace Mathematica).±
en el segundo. Funcionaría conf
, pero a costa de dos bytes.Round[#!/E]+1-Sign@#&
. Valores iniciales molestos ...!Rubí, 27 bytes
~0**n
es más corto que(-1)**n
!fuente
CJam (10 bytes)
Demo en línea .
Esto usa la recurrencia
!n = n !(n-1) + (-1)^n
, de la cual derivaban! / e
y luego descubrí que ya estaba en OEIS.Disección
El ciclo se calcula
(-1)^n !n
, por lo que debemos tomar el valor absoluto al final:fuente
05AB1E , 8 bytes
Pruébalo en línea!
Explicación
fuente
MATLAB, 33 bytes
Función Anonympus que utiliza la fórmula en la Sección 3 de Trastornos y aplicaciones de Mehdi Hassani.
Ejemplo de uso:
fuente
JavaScript (ES6), 26 bytes
Utiliza la relación de recurrencia de la respuesta de @ Laikoni. En ES7 puede guardar un byte utilizando en
+(-1)**n
lugar de-(~n%2|1)
.fuente
PostScript,
817669 bytesAquí hay implementaciones de ambas fórmulas.
n * f (n-1) + (- 1) ^ n
/ f {dup 0 eq {pop 1} {dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub} ifelse} defEsa versión produce un flotador. Si es necesario generar un número entero:
que pesa 73 bytes.
La otra fórmula es un poco más larga: 81 bytes.
(n-1) * (f (n-1) + f (n-2))
Estas funciones obtienen su argumento de la pila y dejan el resultado en la pila.
Puede probar las funciones, ya sea en un archivo o en un mensaje interactivo PostScript (por ejemplo, GhostScript) con
salida
Aquí hay un archivo PostScript completo que muestra el resultado en la pantalla o en la página de una impresora. (Los comentarios en PostScript comienzan con
%
).fuente
-1 3 2 roll exp
es un poco más corto queexch 2 mod 2 mul 1 sub
.exp
: oops: Sin embargo, devuelve un flotante, y creo que necesito generar un número entero para cumplir con la pregunta.cvi
y ahorrar. (Nota: no probado, pero al leer el documento creo que debería funcionar).cvi
funciona, y aún es más corto que mi versión anterior.PHP, 69 bytes
usar de esta manera
a(n) = n*a(n-1) + (-1)^n
fuente
PHP,
5044Corre con
echo <n> | php -nR '<code>
Lo bueno de esto
a(n) = n*a(n-1) + (-1)^n
es que depende solo del valor anterior. Esto permite que se implemente de forma iterativa en lugar de recursiva. Esto ahorra una larga declaración de funciones .-6 bytes por @Titus. Gracias !
fuente
$i++<$argv[1]
. -2 Bytes:for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;
. (-3 bytes con-R
y$argn
.)-R
y$argn
?Mathematica, 40 bytes
Que viene en 31 bytes bajo la codificación ISO 8859-1 predeterminada.
fuente
C, 34 bytes
Explicación:
fuente
R, 47 bytes
Utiliza la misma fórmula que la respuesta de Mego .
Método alternativo, 52 bytes usando la
PerMallows
bibliotecafuente
En realidad , 18 bytes
Pruébalo en línea!
Explicación:
Una versión de 12 bytes que funcionaría si en realidad tuviera más precisión:
Pruébalo en línea!
A diferencia de todas las otras respuestas (a partir de la publicación), esta solución no utiliza ni la fórmula recursiva ni la fórmula de suma. En su lugar, utiliza la siguiente fórmula:
Esta fórmula es relativamente fácil de implementar en realidad:
Ahora, el único problema es que la fórmula solo es positiva
n
. Si intenta usarn = 0
, la fórmula produce incorrectamente0
. Sin embargo, esto se soluciona fácilmente: al aplicar la negación booleana a la entrada y agregarla a la salida de la fórmula, se da la salida correcta para todos los no negativosn
. Por lo tanto, el programa con esa corrección es:fuente
n = 100
),(-1)**n/n!
no se puede representar con flotadores IEEE 754 de doble precisión. Eso es aceptable según el desafío.n=4
...Apilado , 30 bytes
Pruébalo en línea!
Función recursiva simple. Utiliza el hecho de que
!n = not n
paran < 2
. Llamar comon f
.fuente
Alicia ,
2018 bytesPruébalo en línea!
Explicación
Esto utiliza la recursión de Laikoni de respuesta , ! N = n! (N-1) + (-1) n . Similar a la respuesta de Funciton, estoy usando el caso base ! (- 1) = 1 . Ponemos ese 1 en la pila con
1.
. Luego esto...... es solo el marco de E / S decimal habitual. El código principal es en realidad
Desglosado:
fuente