Les nombres sous - factoriels ou rencontres ( A000166 ) sont une séquence de nombres similaires aux nombres factoriels qui apparaissent dans la combinatoire des permutations. En particulier, le n ième sous-factoriel ! N donne le nombre de dérangements d'un ensemble de n éléments. Un dérangement est une permutation dans laquelle aucun élément ne reste dans la même position. La sous-factorielle peut être définie via la relation de récurrence suivante:

!n = (n-1) (!(n-1) + !(n-2))

En fait, la même relation de récurrence vaut pour la factorielle, mais pour la sous-factorielle, nous partons de:

!0 = 1
!1 = 0

^{(Pour la factorielle, nous aurions, bien sûr, 1! = 1. )}

Votre tâche consiste à calculer ! N , étant donné n .

Règles

Comme le factoriel, le sous-factoriel croît très rapidement. C'est bien si votre programme ne peut gérer que les entrées n de telle sorte que ! N puisse être représenté par le type de numéro natif de votre langue. Cependant, votre algorithme doit en théorie fonctionner pour n arbitraire . Cela signifie que vous pouvez supposer que les résultats intégraux et la valeur intermédiaire peuvent être représentés exactement par votre langue. Notez que cela exclut la constante e si elle est stockée ou calculée avec une précision finie.

Le résultat doit être un entier exact (en particulier, vous ne pouvez pas approximer le résultat avec une notation scientifique).

Vous pouvez écrire un programme ou une fonction et utiliser l'une des méthodes standard de réception d'entrée et de sortie.

Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

Il s'agit de code-golf , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Cas de test

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

Funciton , 336 octets

Le nombre d'octets suppose un codage UTF-16 avec BOM.

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

Ceci définit une fonction fqui prend un entier et sort un autre entier à un virage de 90 degrés vers la gauche. Il fonctionne pour des entrées arbitrairement grandes.

Essayez-le en ligne!

Étant donné que c'est Funciton, il est même assez rapide (n = 20 prend environ 14 secondes sur TIO). Le principal ralentissement vient de la double récursivité, car je ne pense pas que l'interpréteur Funciton mémorise automatiquement les fonctions.

Malheureusement, certaines polices à espacement fixe n'espacent pas correctement ♭et / ou n'insèrent pas de petits espaces entre les lignes. Voici une capture d'écran du code de TIO dans toute sa beauté:

Je pense qu'il pourrait être possible de golf ce un peu plus, par exemple en changeant la condition de >0la <1et échangeant les branches du conditionnel, afin que je puisse réutiliser le littéral, ou peut - être en utilisant une formule complètement différente, mais je suis tout à fait satisfait de sa compacité.

Explication

Cela implémente essentiellement la récursivité donnée dans le défi, bien qu'il utilise le cas de base ! (- 1) =! 0 = 1 . n-1 et n-2 sont calculés avec la fonction prédécesseur ♭, et le résultat intermédiaire n-1 est réutilisé à trois endroits. Il n'y a pas grand-chose d'autre, donc je vais rapidement passer en revue le flux de contrôle:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

Il s'agit de l'en-tête de fonction qui émet l'entrée de la fonction n le long de la ligne attachée. Cela atteint immédiatement la jonction en T, qui duplique simplement la valeur.

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

La 0case n'est qu'un littéral numérique. Une jonction à 4 voies calcule deux fonctions: le chemin qui part du bas calcule 0 <n , que nous utiliserons pour déterminer le cas de base. Le chemin qui part à gauche calcule 0 << n (un décalage à gauche), mais nous rejetons cette valeur avec la construction de Starkov .

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

Nous menons cela dans le conditionnel à trois voies ?. Si la valeur est fausse, nous retournons le résultat constant 1. L'extrémité libre à droite de ?est la sortie de fonction. Je le tord de 180 degrés ici, de sorte que l'orientation relative de l'entrée et de la sortie de fsoit plus pratique dans le reste du programme.

Si la condition était vraie, l'autre valeur sera utilisée. Regardons le chemin qui mène à cette branche. (Notez que l'évaluation de Funciton est en fait paresseuse de sorte que cette branche ne sera jamais évaluée si elle n'est pas nécessaire, ce qui rend la récursion possible en premier lieu.)

        ┌─╖ 
      ┐┌┤♭╟┐
      ├┘╘═╝
      │
     ─┴┐

Dans l'autre branche, nous calculons d'abord n-1 , puis divisons le chemin deux fois afin d'obtenir trois copies de la valeur (une pour le coefficient de récurrence, une pour la première sous-factorielle, la dernière pour n-2 ).

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

Comme je l'ai dit, nous décrémentons à nouveau une copie avec une autre ♭, puis nous alimentons récursivement n-1 et n-2 pour ffinalement ajouter les deux résultats ensemble dans le +.

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

Il ne reste plus qu'à multiplier n-1 par ! (N-1) +! (N-2) .

Oasis , 5 octets

Utilise la formule donnée par Martin. Code:

+n<*X

Version disséquée:

+n<*

avec a(0) = 1et a(1) = 0.

Explication, a(n) =:

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

Essayez-le en ligne!

Haskell , 25 octets

f 0=1
f n=n*f(n-1)+(-1)^n

Essayez-le en ligne! Utilise l'autre récurrence de la page OEIS .

Gelée , 7 octets

R=Œ!Ḅċ0

Cette approche construit les dérangements, donc c'est plutôt lent.

Essayez-le en ligne!

Comment ça marche

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.

Brachylog (2), 11 octets

⟦₁{p:?\≠ᵐ}ᶜ

Essayez-le en ligne!

Explication

Il s'agit essentiellement d'une traduction directe de la spécification de l'anglais vers Brachylog (et présente donc l'avantage de pouvoir être facilement modifiée pour gérer de petites modifications de la spécification, telles que la recherche du nombre de dérangements d'une liste spécifique).

⟦₁{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

Langues avec solutions intégrées

Suivant la suggestion de xnor, il s'agit d'une réponse CW dans laquelle des solutions triviales basées sur un seul intégré pour calculer la sous-factorielle ou générer tous les dérangements doivent être éditées.

Mathematica, 12 octets

Subfactorial

Python 3 , 35 32 octets

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

Cela utilise la relation de récurrence ! N = n! (N-1) + (-1) ⁿ de la réponse Haskell de @ Laikoni , avec le cas de base ! 0 = 1 .

Essayez-le en ligne!

M , 9 octets

o2!÷Øe+.Ḟ

Comme vous pouvez le voir en supprimant le Ḟ, M utilise des mathématiques symboliques, il n'y aura donc aucun problème de précision.

Essayez-le en ligne! Pas la solution la plus courte qui ait été publiée, mais rapide .

Comment ça marche

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.

MATL , 9 8 octets

:tY@-!As

De la même manière que la réponse Jelly de @Dennis , cela construit en fait les permutations et compte combien d'entre elles sont des dérangements; c'est donc lent.

Essayez-le en ligne!

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

Mathématiques , 21 octets

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

Je suis très nouveau dans ce domaine et je n'ai aucune idée de ce que je fais ...

Essayez-le en ligne!

Rubis, 27 octets

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

~0**nest plus court que (-1)**n!

CJam (10 octets)

1qi{~*)}/z

Démo en ligne .

Cela utilise la récurrence !n = n !(n-1) + (-1)^n, dont j'ai dérivé n! / epuis découvert que c'était déjà dans OEIS.

Dissection

La boucle calcule (-1)^n !n, nous devons donc prendre la valeur absolue à la fin:

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

05AB1E , 8 octets

΃N*®Nm+

Essayez-le en ligne!

Explication

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

MATLAB, 33 octets

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

Fonction Anonympus qui utilise la formule de la section 3 des Dérangements et applications de Mehdi Hassani.

Exemple d'utilisation:

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

JavaScript (ES6), 26 octets

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

Utilise la relation de récurrence de la réponse de @ Laikoni. Dans ES7, vous pouvez enregistrer un octet en utilisant +(-1)**nau lieu de -(~n%2|1).

PostScript, 81 76 69 octets

Voici les implémentations des deux formules.

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

Cette version génère un flottant. S'il est nécessaire de sortir un entier:

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

qui pèse 73 octets.

L'autre formule est un peu plus longue: 81 octets.

(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

Ces fonctions obtiennent leur argument de la pile et laissent le résultat sur la pile.

Vous pouvez tester les fonctions, soit dans un fichier soit à une invite PostScript interactive (par exemple GhostScript) avec

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

sortie

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

Voici un fichier PostScript complet qui rend la sortie à l'écran ou sur une page d'imprimante. (Les commentaires dans PostScript commencent par %).

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

PHP, 69 octets

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

utiliser de cette façon a(n) = n*a(n-1) + (-1)^n

PHP, 50 44

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

Courir avec echo <n> | php -nR '<code>

La beauté de a(n) = n*a(n-1) + (-1)^nc'est que cela ne dépend que de la valeur précédente. Cela lui permet d'être implémenté de manière itérative plutôt que récursive. Cela enregistre une longue fonction déclaration de .

-6 octets par @Titus. Merci !

Mathematica, 40 octets

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

Ce qui arrive à 31 octets sous l'encodage ISO 8859-1 par défaut.

C, 34 octets

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

Explication:

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

R, 47 octets

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

Utilise la même formule que la réponse de Mego .

Méthode alternative, 52 octets utilisant la PerMallowsbibliothèque

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

En fait , 18 octets

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

Essayez-le en ligne!

Explication:

;!@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

Une version de 12 octets qui fonctionnerait si en fait avait plus de précision:

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

Essayez-le en ligne!

Contrairement à toutes les autres réponses (au moment de la publication), cette solution n'utilise ni la formule récursive ni la formule de sommation. Au lieu de cela, il utilise la formule suivante:

Cette formule est relativement facile à mettre en œuvre en fait:

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

Maintenant, le seul problème est que la formule ne vaut que pour le positif n. Si vous essayez d'utiliser n = 0, la formule donne incorrectement 0. Ceci est facilement corrigé, cependant: en appliquant la négation booléenne à l'entrée et en ajoutant qu'à la sortie de la formule, la sortie correcte est donnée pour tous les non négatifs n. Ainsi, le programme avec cette correction est:

;!╠@/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

Empilé , 30 octets

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

Essayez-le en ligne!

Fonction récursive simple. Utilise le fait que !n = not npour n < 2. Appelez le n f.

Alice , 20 18 octets

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

Essayez-le en ligne!

Explication

Celui - ci utilise la récursion de réponse de Laikoni , ! N = n! (N-1) + (-1) ⁿ . Semblable à la réponse de Funciton, j'utilise le cas de base ! (- 1) = 1 . Nous avons mis ce 1 sur la pile avec 1.. Ensuite ceci...

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

... est juste le cadre d'E / S décimal habituel. Le code principal est en fait

&wq*eqE+]k

En panne:

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