Comprendre les fonctions génératrices par un exemple classique

Les fonctions génératrices sont un outil fondamental en combinatoire analytique. Pour illustrer leur mécanisme, considérons le problème suivant : trouver le nombre de solutions entières non négatives de l'équation x + 2y = 10.

Du point de vue combinatoire, chaque variable peut prendre une infinité de valeurs. L'idée est de représenter toutes les possibilités sous forme de séries entières. Pour x, la série est (1 + z + z² + z³ + ...). Pour y, la contribution est (1 + z² + z⁴ + z⁶ + ...) puisque chaque y multiplie la valeur 2. Le produit de ces deux séries engendre toutes les combinaisons :

(1 + z + z² + z³ + ...) × (1 + z² + z⁴ + z⁶ + ...)

Le coefficient de zⁿ dans ce produit donne précisément le nombre de solutions à l'équation x + 2y = n. Cette construction peut être généralisée à tout système d'équations linéaires à coefficients entiers.

Application au problème 1028 : Décompositions en somme

Le problème 1028 demande de calculer le nombre de manières d'écrire un entier N comme une somme de termes, chacun variant entre 1 et N. Cela équivaut à trouver le coefficient de zᴺ dans le produit de N séries géométriques. Voici une implémentation optimisée utilisant une approche itérative par convolution :

import java.util.Scanner;

public class DecompositionCounter {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            int target = input.nextInt();
            int[] currentCoeffs = new int[target + 1];
            int[] tempCoeffs = new int[target + 1];
            
            // Initialisation pour le premier terme (variant de 0 à target)
            for (int i = 0; i <= target; i++) {
                currentCoeffs[i] = 1;
            }
            
            // Convolution successive pour les termes suivants
            for (int term = 2; term <= target; term++) {
                for (int exponent = 0; exponent <= target; exponent++) {
                    for (int step = 0; exponent + step * term <= target; step++) {
                        tempCoeffs[exponent + step * term] += currentCoeffs[exponent];
                    }
                }
                
                // Mise à jour et réinitialisation
                System.arraycopy(tempCoeffs, 0, currentCoeffs, 0, target + 1);
                java.util.Arrays.fill(tempCoeffs, 0);
            }
            System.out.println(currentCoeffs[target]);
        }
    }
}

Application au problème 1398 : Combinaisons de carrés parfaits

Dans ce problème, les termes disponibles sont les carrés parfaits (1, 4, 9, 16, ...). L'approche est analogue, mais on doit adapter les pas d'incrémentation. L'algorithme ci-dessous calcule le nombre de représentations d'un entier comme somme de carrés :

import java.util.Scanner;

public class SquareSumsCounter {
    private static final int[] SQUARES = new int[18];
    
    static {
        for (int i = 1; i < 18; i++) {
            SQUARES[i] = i * i;
        }
    }
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            int limit = input.nextInt();
            if (limit == 0) break;
            
            int[] coeffs = new int[limit + 1];
            int[] buffer = new int[limit + 1];
            coeffs[0] = 1;
            
            // Traitement de chaque carré parfait
            for (int idx = 1; idx < SQUARES.length && SQUARES[idx] <= limit; idx++) {
                int square = SQUARES[idx];
                for (int currentSum = 0; currentSum <= limit; currentSum++) {
                    if (coeffs[currentSum] == 0) continue;
                    for (int multiple = 0; currentSum + multiple * square <= limit; multiple++) {
                        buffer[currentSum + multiple * square] += coeffs[currentSum];
                    }
                }
                
                // Fusion des résultats
                System.arraycopy(buffer, 0, coeffs, 0, limit + 1);
                java.util.Arrays.fill(buffer, 0);
            }
            System.out.println(coeffs[limit]);
        }
    }
}

Application au problème 1171 : Partition d'objets en sous-ensembles équilibrés

Ce problème consiste à répartir des objets de différentes valeurs en deux groupes dont les sommes sont aussi proches que possible. L'approche classique utilise une fonction génératrice pour cacluler toutes les sommes possibles avec la première moitié des objets. On cherche ensuite la somme la plus proche de la moitié totale :

import java.util.Scanner;

public class BalancedPartition {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNextLine()) {
            String line = input.nextLine().trim();
            if (line.isEmpty()) continue;
            int itemCount = Integer.parseInt(line);
            if (itemCount < 0) break;
            
            int[] values = new int[itemCount];
            int[] counts = new int[itemCount];
            int totalSum = 0;
            
            for (int i = 0; i < itemCount; i++) {
                String[] parts = input.nextLine().trim().split("\\s+");
                values[i] = Integer.parseInt(parts[0]);
                counts[i] = Integer.parseInt(parts[1]);
                totalSum += values[i] * counts[i];
            }
            
            // Calcul des sommes possibles avec les premiers objets
            int[] achievableSums = new int[totalSum / 2 + 1];
            achievableSums[0] = 1;
            
            for (int objIndex = 0; objIndex < itemCount; objIndex++) {
                int value = values[objIndex];
                int maxCount = counts[objIndex];
                
                for (int sum = totalSum / 2; sum >= 0; sum--) {
                    if (achievableSums[sum] == 0) continue;
                    for (int used = 1; used <= maxCount; used++) {
                        int newSum = sum + used * value;
                        if (newSum > totalSum / 2) break;
                        achievableSums[newSum] += achievableSums[sum];
                    }
                }
            }
            
            // Recherche de la partition la plus équilibrée
            int half = totalSum / 2;
            while (half >= 0 && achievableSums[half] == 0) {
                half--;
            }
            System.out.println((totalSum - half) + " " + half);
        }
    }
}