Cette semaine, c'est Morgan qui vous propose un #KataOfTheWeek : Calcul de sous-factorielles

Briefing du Kata : En mathématiques, la factorielle d'un entier n est le produit de tous les nombres positifs inférieurs ou égaux à n et elle est notée n!. Par exemple :

  • 3! = 3 * 2 * 1 = 6
  • 5! = 5 * 4 * 3 * 2 * 1 = 120

Plus concrètement, la factorielle représente aussi le nombre de permutations possibles d'un ensemble d'élément. C'est-à-dire que la factorielle de 5 peut représenter le nombre de possibilités pour garer 5 voitures sur 5 places différentes.

La sous-factorielle, aussi appelé dérangement est un peu différente. Elle représente l'ensemble des permutations d'un ensemble d'élément telles qu'aucun des éléments ne se retrouve à sa place initiale. Elle est notée !n.

En reprenant l'exemple des voitures, si on a 3 places initialement associées à 3 voitures :

Place 1Place 2Place 3V1V2V3

Les permutations valables sont donc :

Place 1Place 2Place 3V2V3V1V3V1V2

Donc !3 = 2

Quelques valeurs :

  • !0 = 1
  • !1 = 0
  • !2 = 1
  • !3 = 2
  • !4 = 9

L'objectif de ce kata est de créer un algorithme récursif qui à partir d'une entrée n (entier positif) affiche en sortie la valeur de de !n (sous-factorielle de n).

Votre programme doit être capable de calculer les valeurs suivantes :

!5 = 44
!10 = 1334961
!15 = 481066515734

Saurez-vous résoudre le problème ?

Bon courage ! Retrouvez la solution dans cet article 😉