On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Morgan en début de semaine !

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

A bientôt pour un nouveau #KataOfTheWeek !