Un petit souvenir des séminaires avec les nombres de Catalan

Cette semaine, c'est Alexandre qui vous propose un #KataOfTheWeek : Les nombres de Catalan

Briefing du Kata : Les nombres de Catalan apparaissent dans divers domaines des mathématiques dans des problématiques de dénombrement… Contrairement à ce que leur nom indique, ils n'ont rien de catalan. Ils sont nommés en l'honneur du mathématicien Belge Éponyme.

Je vous propose de faire un petit peu de maths puis d'implémenter différentes solution et de comparer leurs performances.

Les nombres de Catalan apparaissent par exemple dans le décompte du nombre d'association de paires de parenthèses, c'est aussi la manière la plus simple de faire apparaître une hypothèse de récurrence : n: nombre de paires de parenthèses Cn: nombre de possibilité d'association de ces paires n = 0 - - Cn = 1

n = 1 - () - Cn = 1

n = 2 - (()), ()() - Cn = 2

n = 3 - ((())), (()()), (())(), ()(()), ()()() - Cn = 5

n = 4 - (((()))), ((()())), ((())()), (()(())), (()()()), … - Cn = 14

Pour ceux qui voudraient retrouver la solution de récurrence, arrêtez vous ici et prenez un petit bout de papier.

…

Pour les autres vous trouverez la relation de récurrence suivante:

C'est parti :

• implémente cette fonction
• calcule sa complexité
• teste le calcul sur des valeurs élevées de n (pas la peine de trop s'énerver non plus)

On voit que la méthode récursive "simple" s'effondre assez rapidement.

Comparons maintenant la solution récursive à l'analytique :

(Rappelez vous que factoriel 21 explose MAX_LONG…)

Il existe une autre relation de récurrence beaucoup plus performante :

Compare ces différentes méthodes, laquelle est la plus performante, la plus élégante…?

Saurez-vous résoudre le problème ?

Bon courage !

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

import java.math.BigInteger;

public class Katalan {

    private static BigInteger C0 = BigInteger.ONE;

    public static void main(String... args) {
        BigInteger cn;
        long n = 15, startTime, elapsedTime;
        System.out.println("KATA-LAN -  n = " + n);

        //CAS RÉCURSIF
        startTime = System.nanoTime();
        cn = catalanRecursive(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS RÉCURSIF: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");

        //CAS RÉCURSIF BIS
        startTime = System.nanoTime();
        cn = catalanRecursiveBis(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS RÉCURSIF BIS: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");

        //CAS ANALYTIQUE
        startTime = System.nanoTime();
        cn = catalanAnalytic(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS ANALYTIQUE: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");
    }

    public static BigInteger catalanRecursive(long n) {
        if (n == 0) return C0;
        BigInteger sum = BigInteger.ZERO;
        for (long i = 0; i < n; i++) {
            sum = sum.add(catalan_recursive(i).multiply(catalanRecursive(n - 1 - i)));
        }
        return sum;
    }

    public static BigInteger catalanRecursiveBis(long n) {
        if (n == 0) return C0;
        return BigInteger.valueOf(2 * (2 * n - 1))
                .multiply(catalanRecursiveBis(n - 1))
                .divide(BigInteger.valueOf(n + 1));
    }

    public static BigInteger catalanAnalytic(long n) {
        return factorial(2 * n).divide(factorial(n + 1).multiply(factorial(n)));
    }

    private static BigInteger factorial(long n) {
        if (n <= 1 ) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n - 1));
    }
}

Votre équipe TakiVeille