Calcul de sous-factorielles

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 !

Et voici une solution proposée par l'auteur :

Si vous avez cherché sur Internet il est facile de trouver la formule récursive d'une sous-factorielle:

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

L'implémentation est finalement très similaire à l'algorithme de la factorielle. Mais d'où vient cette formule ?

Reprenons l'exemple des voitures, initialement chaque voiture à sa place:

Place 1Place 2Place 3Place 4V1V2V3V4

Combien de dérangements sont possibles ?

Faisons l'hypothèse que la voiture 1 prenne la place de la voiture 2:

Place 1Place 2Place 3Place 4V1

On peut alors considérer 2 situations:

1) La voiture 2 prends la place de la voiture 1 2) La voiture 2 ne prends pas la place de la voiture 1

Ces 2 situations s'excluent mutuellement et si on calcule leur propre dérangement on pourra les additionner.

Si la voiture 2 prends la place de la voiture 1 alors les deux voitures ont simplement inversé leurs places:

Place 1Place 2Place 3Place 4V2V1??

Le nombre de dérangements possibles en considérant cette situation est donc réduit au nombre de dérangements des voitures restantes, ici !2.

Dans l'autre cas, la voiture 2 ne doit absolument pas être sur la place 1 pour ne pas entrer en conflit avec la situation précédente. Cela revient à considérer la voiture 2 comme étant une "fausse voiture 1" car elle ne peut pas être sur la place 1.

Place 1Place 2Place 3Place 4?V1??

Le nombre de dérangements possibles est alors le nombre de dérangements des 3 voitures restantes, !3.

En générlisant pour n voitures, on a !(n-2) dérangements possibles dans la situation 1 et !(n-1) dérangements possibles dans la situation 2.

La somme des dérangements donne donc !(n-1) + !(n-2).

Au tout début, nous avons aussi fait l'hypothèse que la voiture 1 prenait la place de la voiture 2. La voiture 1 aurait pu prendre n'importe quelle autre place sauf la place 1. Elle avait donc (n-1) possibilités de placement. Dans les cas on aurait obtenu la même somme de dérangements pour toutes les hypothèses, on peut donc multiplier la somme des dérangements des deux situations par (n-1).

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

Voici un algorithme de sous-factorielle en Python 3 :

import sys

def subfactorial(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    return (n-1) * (subfactorial(n-1) + subfactorial(n-2))

if __name__ == "__main__":
    print(subfactorial(int(sys.argv[1])))

Votre équipe TakiVeille