Deranged! Combinatorics: Compute the Subfactorial

25

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 , 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
Martin Ender
fuente
Relacionado.
Martin Ender

Respuestas:

19

Funciton , 336 bytes

El recuento de bytes supone la codificación UTF-16 con BOM.

┌─╖┌─╖  ┌─╖ 
│f╟┤♭╟┐┌┤♭╟┐
╘╤╝╘═╝├┘╘═╝├────┐
 │┌─╖ │ ┌┐┌┘╔═╗╓┴╖
 ││f╟─┴┐└┴┼─╢0║║f║
 │╘╤╝  │  │ ╚═╝╙─╜
 │┌┴╖ ┌┴╖┌┴╖ ╔═╗
 ││+╟┐│×╟┤?╟┐║1║
 │╘╤╝│╘╤╝╘╤╝┘╚╤╝
 └─┘ └─┘  └───┘

Esto define una función fque 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:

ingrese la descripción de la imagen aquí

Creo que podría ser posible jugar al golf un poco más, por ejemplo, cambiando la condición de >0a <1e 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:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

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.

        ┌┐┌┘╔═╗
        └┴┼─╢0║
          │ ╚═╝

El 0cuadro 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 .

         ┌┴╖ ╔═╗
         ┤?╟┐║1║
         ╘╤╝┘╚╤╝
          └───┘

Llevamos esto al condicional de tres vías ?. Si el valor es falso, devolvemos el resultado constante 1. 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 salida fsea ​​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 ).

┌─╖┌─╖
│f╟┤♭╟
╘╤╝╘═╝
 │┌─╖
 ││f╟
 │╘╤╝
 │┌┴╖
 ││+╟
 │╘╤╝
 └─┘ 

Como dije, decrementamos una copia nuevamente con otra , luego alimentamos tanto n-1 como n-2 recursivamente fy finalmente agregamos los dos resultados juntos en el +.

       ┐
       │
      ┌┴╖
     ┐│×╟
     │╘╤╝
     └─┘

Todo lo que queda es multiplicar n-1 por ! (N-1) +! (N-2) .

Martin Ender
fuente
13

Oasis , 5 bytes

Utiliza la fórmula dada por Martin. Código:

+n<*X

Versión disecada:

+n<*

con a(0) = 1y a(1) = 0.

Explicación, a(n) =:

+       # Add the previous two terms, a(n - 1) + a(n - 2).
 n<     # Compute n - 1.
   *    # Multiply the top two elements.

Pruébalo en línea!

Adnan
fuente
Buen truco usando X:-) Por cierto, ¿implementaste esto todavía? Uno de estos días no podremos escapar simplemente cambiando los valores iniciales
Luis Mendo
@LuisMendo Sí, lo hice! Se utiliza como un indicador de comando ( aquí hay un enlace a la página de información). Gracias por la sugerencia :).
Adnan
7

Jalea , 7 bytes

R=Œ!Ḅċ0

Este enfoque construye los trastornos, por lo que es bastante lento.

Pruébalo en línea!

Cómo funciona

R=Œ!Ḅċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
  Œ!     Yield all permutations of [1, ..., n].
 =       Perform elementwise comparison of [1, ..., n] and each permutation.
    Ḅ    Unbinary; convert each result from base 2 to integer. This yields 0 for
         derangements, a positive value otherwise.
     ċ0  Count the number of zeroes.
Dennis
fuente
7

Brachylog (2), 11 bytes

⟦₁{p:?\≠ᵐ}ᶜ

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

⟦₁{p:?\≠ᵐ}ᶜ
⟦₁           Start with a list of {the input} distinct elements
  {      }ᶜ  Then count the number of ways to
   p         permute that list
      \      such that taking corresponding elements
    :?       in {the permutation} and the list of distinct elements
       ≠     gives different elements
        ᵐ    at every position

fuente
5

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

Subfactorial
Martin Ender
fuente
suspiro Mathematica ...
epicbob57
5

Python 3 , 35 32 bytes

f=lambda n:n<1or(-1)**n+n*f(n-1)

Esto 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!

Dennis
fuente
Creo que también se puede utilizar la otra ecuación dada aquí , lo que ahorraría dos bytes: f=lambda n:n<1or n*f(n-1)+(-1)**n.
Adnan
1
Tres bytes con un poco de reordenamiento. ;)
Dennis
1
La parte divertida de esta recurrencia es que si vuelve a colocar el caso base 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).
Martin Ender
5

M , 9 bytes

o2!÷Øe+.Ḟ

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

o2!÷Øe+.Ḟ  Main link. Argument: n

o2         Replace input 0 with 2, as the following formula fails for 0.
  !        Compute the factorial of n or 2.
   ֯e     Divide the result by e, Euler's natural number.
      +.   Add 1/2 to the result.
        Ḟ  Floor; round down to the nearest integer.
Dennis
fuente
5

MATL , 9 8 bytes

:tY@-!As

De 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!

:     % Input n implicitly: Push [1 2 ... n]
t     % Duplicate 
Y@    % Matrix of all permutations, each on a row
-     % Element-wise subtract. A zero in a row means that row is not a derangement
!     % Transpose
A     % True for columns that don't contain zeros
s     % Sum. Implicitly display
Luis Mendo
fuente
3

Matemáticas , 21 bytes

Round@If[#>0,#!/E,1]&

Soy muy nuevo en esto y no tengo idea de lo que estoy haciendo ...

Pruébalo en línea!

Dennis
fuente
1
Dos alternativas en el mismo número de bytes: 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).
Martin Ender
El primero funciona bien ( creo que sé lo que hace), pero Mathics no parece admitir ±en el segundo. Funcionaría con f, pero a costa de dos bytes.
Dennis
Otro al mismo recuento de bytes: Round[#!/E]+1-Sign@#&. Valores iniciales molestos ...!
Greg Martin
3

Rubí, 27 bytes

f=->n{n<1?1:n*f[n-1]+~0**n}

~0**nes más corto que (-1)**n!

m-chrzan
fuente
3

CJam (10 bytes)

1qi{~*)}/z

Demo en línea .

Esto usa la recurrencia !n = n !(n-1) + (-1)^n, de la cual derivaba n! / ey 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:

1     e# Push !0 to the stack
qi{   e# Read an integer n and loop from 0 to n-1
  ~   e#   Bitwise not takes i to -(i+1), so we can effectively loop from 1 to n
  *   e#   Multiply
  )   e#   Increment
}/
z     e# Take the absolute value
Peter Taylor
fuente
2

05AB1E , 8 bytes

΃N*®Nm+

Pruébalo en línea!

Explicación

Î         # initialize stack with 0 and input
 ƒ        # for N in range [0 ... input]:
  N*      # multiply top of stack with N
    ®Nm   # push (-1)^N
       +  # add
Emigna
fuente
2

MATLAB, 33 bytes

@(n)(-1)^n*hypergeom([1 -n],[],1)

Función Anonympus que utiliza la fórmula en la Sección 3 de Trastornos y aplicaciones de Mehdi Hassani.

Ejemplo de uso:

>> @(n)(-1)^n*hypergeom([1 -n],[],1)
ans = 
    @(n)(-1)^n*hypergeom([1,-n],[],1)
>> ans(6)
ans =
   265
Luis Mendo
fuente
2

JavaScript (ES6), 26 bytes

f=n=>!n||n*f(n-1)-(~n%2|1)

Utiliza la relación de recurrencia de la respuesta de @ Laikoni. En ES7 puede guardar un byte utilizando en +(-1)**nlugar de -(~n%2|1).

Neil
fuente
2

PostScript, 81 76 69 bytes

Aquí 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} def

/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

Esa versión produce un flotador. Si es necesario generar un número entero:

/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp cvi add}ifelse}def

que pesa 73 bytes.

La otra fórmula es un poco más larga: 81 bytes.

(n-1) * (f (n-1) + f (n-2))

/f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

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

0 1 12{/i exch def [i i f] ==}for

salida

[0 1]
[1 0.0]
[2 1.0]
[3 2.0]
[4 9.0]
[5 44.0]
[6 265.0]
[7 1854.0]
[8 14833.0]
[9 133496.0]
[10 1334961.0]
[11 14684570.0]
[12 176214848.0]

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

%!PS-Adobe-3.0

% (n-1)*(f(n-1)+f(n-2))
% /f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

% n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

% 0 1 12{/i exch def [i i f] ==}for

/FS 16 def              %font size
/LM 5 def               %left margin
/numst 12 string def    %numeric string buffer

/Newline{currentpoint exch pop FS sub LM exch moveto}def
/Courier findfont FS scalefont setfont
LM 700 moveto

(Subfactorials) Newline
0 1 12{
    dup numst cvs show (: ) show f numst cvs show Newline
}for
showpage
quit
PM 2Ring
fuente
1
-1 3 2 roll expes un poco más corto que exch 2 mod 2 mul 1 sub.
Peter Taylor
@PeterTaylor ¡Así es! :) Me olvidé de exp: oops: Sin embargo, devuelve un flotante, y creo que necesito generar un número entero para cumplir con la pregunta.
PM 2Ring
1
Creo que todavía puedes tirar cviy ahorrar. (Nota: no probado, pero al leer el documento creo que debería funcionar).
Peter Taylor
@PeterTaylor Sí, cvifunciona, y aún es más corto que mi versión anterior.
PM 2Ring
1

PHP, 69 bytes

function f($i){return$i>1?$i*f($i-1)+(-1)**$i:1-$i;}echo f($argv[1]);

usar de esta manera a(n) = n*a(n-1) + (-1)^n

Jörg Hülsermann
fuente
1
Solo necesita asignar la función, no el programa completo, para que pueda eliminar los últimos 17 caracteres. Hay un ahorro adicional al no ingresar la carcasa especial 1. Creo que los dos ahorros lo reducen a 47 bytes.
Peter Taylor
1

PHP, 50 44

for(;$i++<$argn;)$n=++$n*$i-$i%2*2;echo$n+1;

Corre con echo <n> | php -nR '<code>

Lo bueno de esto a(n) = n*a(n-1) + (-1)^nes 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 !

Christoph
fuente
-1 byte: $i++<$argv[1]. -2 Bytes: for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;. (-3 bytes con -Ry $argn.)
Titus
@Titus alguien se aburrió? : D, ¿te importaría darme un ejemplo para -Ry $argn?
Christoph
1
No aburrido, pero con ganas de jugar al golf. Ver php.net/manual/de/features.commandline.options.php: echo <input> | php -nR '<código>'. ejemplo: codegolf.stackexchange.com/a/113046
Titus el
1
@Titus ¿Lo entendí bien? ;-)
Christoph
0

Mathematica, 40 bytes

±0=1;±1=0;±n_:=(n-1)(±(n-1)+±(n-2))

Que viene en 31 bytes bajo la codificación ISO 8859-1 predeterminada.

Un simmons
fuente
0

C, 34 bytes

a(n){return n?n*a(n-1)-n%2*2+1:1;}

Explicación:

a(n){                            } define a function called a of n
     return                     ;  make the function evaluate to...
            n?                :1   set the base case of 1 when n is 0
              n*a(n-1)             first half of the formula on the page
                      -n%2*2+1     (-1)**n
Bijan
fuente
0

R, 47 bytes

n=scan();`if`(!n,1,floor(gamma(n+1)/exp(1)+.5))

Utiliza la misma fórmula que la respuesta de Mego .

Método alternativo, 52 bytes usando la PerMallowsbiblioteca

n=scan();`if`(!n,1,PerMallows::count.perms(n,n,'h'))
Giuseppe
fuente
0

En realidad , 18 bytes

;!@ur⌠;!@0Dⁿ/⌡MΣ*≈

Pruébalo en línea!

Explicación:

;!@ur⌠;!@0Dⁿ/⌡MΣ*≈
;                   duplicate input
 !                  n!
  @ur               range(0, n+1) (yields [0, n])
     ⌠;!@0Dⁿ/⌡M     for each i in range:
      ;               duplicate i
       !              i!
        @0Dⁿ          (-1)**i
            /         (-1)**i/i!
               Σ    sum
                *   multiply sum by n!
                 ≈  floor into int

Una versión de 12 bytes que funcionaría si en realidad tuviera más precisión:

;!╠@/1½+L@Y+

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:

fórmula de trastorno

Esta fórmula es relativamente fácil de implementar en realidad:

!╠@/1½+L
!         n!
 ╠        e
  @/      divide n! by e
    1½+   add 0.5
       L  floor

Ahora, el único problema es que la fórmula solo es positiva n. Si intenta usar n = 0, la fórmula produce incorrectamente 0. 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 negativos n. Por lo tanto, el programa con esa corrección es:

;!╠@/1½+L@Y+
;             duplicate input
 !            n!
  ╠           e
   @/         divide n! by e
     1½+      add 0.5
        L     floor
         @Y   boolean negate the other copy of the input (1 if n == 0 else 0)
           +  add
Mego
fuente
Sigue dando respuestas negativas para mí ...
Leaky Nun
@LeakyNun Eso se debe a los límites de precisión. Para entradas grandes (alrededor 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.
Mego
Incluso para n=4...
Leaky Nun
@LeakyNun Oh. No sé por qué estaba usando la división de pisos. Arreglando ahora.
Mego
16 bytes
Leaky Nun
0

Apilado , 30 bytes

[:[#-::#-f\f+*]$not,\2<# !]@:f

Pruébalo en línea!

Función recursiva simple. Utiliza el hecho de que !n = not npara n < 2. Llamar como n f.

Conor O'Brien
fuente
0

Alicia , 20 18 bytes

1/o
k\i@/&wq*eqE+]

Prué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...

.../o
...\i@/...

... es solo el marco de E / S decimal habitual. El código principal es en realidad

&wq*eqE+]k

Desglosado:

&w    Push the current IP address N times to the return address stack, which
      effectively begins a loop which will be executed N+1 times.
  q     Push the position of the tape head, which we're abusing as the
        iterator variable n.
  *     Multiply !(n-1) by n.
  e     Push -1.
  q     Retrieve n again.
  E     Raise -1 to the nth power.
  +     Add it to n*!(n-1).
  ]     Move the tape head to the right.
k     Jump back to the w, as long as there is still a copy of the return
      address on the return address stack. Otherwise, do nothing and exit
      the loop.
Martin Ender
fuente