Research_LaBRI: Random Generation of Combinatorial Objects - Hadamard Product under Boltzmann Sampling

Français | English

---

🇫🇷 Version Française

📚 Description du Projet

Ce dépôt contient les travaux de recherche menés lors d'un stage au LaBRI (Laboratoire Bordelais de Recherche en Informatique) sous la direction de Philippe Duchon.
Le projet explore la génération aléatoire d'objets combinatoires via la méthode de Boltzmann, avec un focus particulier sur le produit de Hadamard.

---

🎯 Objectifs de la Recherche

• Implémenter l'algorithme de Sportiello pour l'échantillonnage exact du produit de Hadamard
• Développer des générateurs de Boltzmann pour diverses structures combinatoires
• Analyser les propriétés théoriques des méthodes d'échantillonnage
• Valider expérimentalement les distributions générées

---

🏗️ Structure du Dépôt

Research_LaBRI/
├── cpp_implementations/
│   ├── simu_boltzmann.cpp      # Échantillonnage Boltzmann-Hadamard en C++
│   └── simu.cpp                # Générateur LFSR pour tests randomisés
├── python_implementations/
│   ├── Sportellio_algorithm.py # Implémentation complète de l'algorithme de Sportiello
│   ├── sportellio_algo.py      # Version simplifiée pour tests
│   └── simu_hadamard.py        # Simulations basiques et distributions
├── research_documents/
│   ├── Stage_CombAlog-3.pdf    # Rapport détaillé du recherche (58 pages)
│   └── StageL3_2025_Duchon.pdf # Proposition de sujet originale            
└── README.md

---

🔬 Algorithmes Implémentés

1. Algorithme de Sportiello (Poissonisation)

def sportiello_random(lam=5.0, mu=5.0):
    """Génération par poissonisation avec paramètres optimaux"""
    x = rejet(lam, mu)
    while x is None:
        x = rejet(lam, mu)
    return x

2. Générateurs de Boltzmann

• Arbres binaires : Boltzmann_arbre_binaire(z)
• Mots de Fibonacci : Boltzmann_grammaire_de_fibonacci(z)
• Marches aléatoires : Boltzmann_random_walk_iterative(z)

3. Produit de Hadamard Adapté

def Boltzmann_Sportiello_Random(len1, len2, alea1, alea2, z1, z2, lam=5.0, mu=5.0):
    """Génération de paires d'objets de même taille via Sportiello"""

---

🚀 Guide d'Utilisation

Prérequis

# Pour les implémentations Python
pip install numpy matplotlib networkx

# Pour les implémentations C++
g++ --version  # Version C++11 ou supérieure

Exécution des Simulations

Code Python Principal :

cd python_implementations
python Sportellio_algorithm.py

Code C++ :

cd cpp_implementations
g++ -std=c++11 -O2 simu_boltzmann.cpp -o boltzmann_sampler
./boltzmann_sampler

---

📊 Résultats et Visualisations

Le projet inclut des fonctionnalités de visualisation pour :

• Arbres binaires : représentation graphique des structures générées
• Marches aléatoires : trajectoires 2D dans $\mathbb{Z}^2$
• Distributions de taille : analyse statistique des objets générés

Exemple de visualisation :

plot_binary_tree(arbre, "Arbre Boltzmann")
plot_random_walk(marche)

---

🧮 Fondements Mathématiques

Loi de Boltzmann

$$ P_x(\gamma) = \frac{x^{|\gamma|}}{C(x)} $$

Produit de Hadamard

$$ A \odot B = \bigcup_{n \ge 0} (A_n \times B_n) $$

Poissonisation (Sportiello)

$$ C_n^A \sim P(\lambda p_n), \quad C_n^B \sim P(\mu q_n) $$

---

📈 Résultats Expérimentaux

• Validation des distributions théoriques vs empiriques
• Optimisation des paramètres $\lambda, \mu$ pour la probabilité de succès
• Complexité : $\mathbb{E}[\text{essais}] = \frac{1}{P_{\text{succès}}}$

---

👥 Équipe de Recherche

• Nasr-allah HITAR — Chercheur stagiaire
• Philippe DUCHON — Directeur de recherche (LaBRI)
• Laboratoire : LaBRI, Université de Bordeaux

---

📖 Références Bibliographiques

• Duchon et al. "Boltzmann Samplers for the Random Generation of Combinatorial Structures" (2004)
• Sportiello, A. "Improved Boltzmann sampling for the Hadamard product of distributions" (2016)
• Pivoteau, C. "Génération aléatoire sous modèle de Boltzmann: le cas non-étiqueté" (2008)
• Flajolet, P. & Sedgewick, R. "Analytic Combinatorics" (2009)

---

🔍 Perspectives Futures

• Extension aux classes combinatoires étiquetées
• Optimisation automatique des paramètres de Poisson
• Applications en bio-informatique et compilation

---

🇬🇧 English Version

📚 Project Description

This repository contains research work conducted at LaBRI (Bordeaux Computer Science Research Laboratory) under the supervision of Philippe Duchon.
The project explores random generation of combinatorial objects using Boltzmann sampling, with particular focus on the Hadamard product problem.

---

🎯 Research Objectives

• Implement Sportiello's algorithm for exact Hadamard product sampling
• Develop Boltzmann samplers for various combinatorial structures
• Analyze theoretical properties of sampling methods
• Validate experimentally the generated distributions

---

🏗️ Repository Structure

Research_LaBRI/
├── cpp_implementations/
│   ├── simu_boltzmann.cpp      # Boltzmann-Hadamard sampling in C++
│   └── simu.cpp                # LFSR generator for randomized tests
├── python_implementations/
│   ├── Sportellio_algorithm.py # Complete implementation of Sportiello's algorithm
│   ├── sportellio_algo.py      # Simplified version for testing
│   └── simu_hadamard.py        # Basic simulations and distributions
├── research_documents/
│   ├── Stage_CombAlog-3.pdf    # Detailed research report (58 pages)
│   └── StageL3_2025_Duchon.pdf # Original internship proposal
└── README.md

---

🔬 Implemented Algorithms

1. Sportiello's Algorithm (Poissonization)

def sportiello_random(lam=5.0, mu=5.0):
    """Generation via poissonization with optimal parameters"""
    x = rejet(lam, mu)
    while x is None:
        x = rejet(lam, mu)
    return x

2. Boltzmann Samplers

• Binary trees : Boltzmann_arbre_binaire(z)
• Fibonacci words : Boltzmann_grammaire_de_fibonacci(z)
• Random walks : Boltzmann_random_walk_iterative(z)

3. Adapted Hadamard Product

def Boltzmann_Sportiello_Random(len1, len2, alea1, alea2, z1, z2, lam=5.0, mu=5.0):
    """Generation of object pairs with same size via Sportiello"""

---

🚀 Usage Guide

Prerequisites

# For Python implementations
pip install numpy matplotlib networkx

# For C++ implementations
g++ --version  # C++11 or higher required

Running Simulations

Python Main Code:

cd python_implementations
python Sportellio_algorithm.py

C++ Code:

cd cpp_implementations
g++ -std=c++11 -O2 simu_boltzmann.cpp -o boltzmann_sampler
./boltzmann_sampler

---

📊 Results and Visualizations

The project includes visualization features for:

• Binary trees: graphical representation of generated structures
• Random walks: 2D trajectories in $\mathbb{Z}^2$
• Size distributions: statistical analysis of generated objects

Example:

plot_binary_tree(tree, "Boltzmann Tree")
plot_random_walk(walk)

---

🧮 Mathematical Foundations

Boltzmann Distribution

$$ P_x(\gamma) = \frac{x^{|\gamma|}}{C(x)} $$

Hadamard Product

$$ A \odot B = \bigcup_{n \ge 0} (A_n \times B_n) $$

Poissonization (Sportiello)

$$ C_n^A \sim P(\lambda p_n), \quad C_n^B \sim P(\mu q_n) $$

---

📈 Experimental Results

• Validation of theoretical vs empirical distributions
• Optimization of $\lambda, \mu$ parameters for success probability
• Complexity: $\mathbb{E}[\text{trials}] = \frac{1}{P_{\text{success}}}$

---

👥 Research Team

• Nasr-allah HITAR — Main researche intern
• Philippe DUCHON — Research supervisor (LaBRI)
• Laboratory: LaBRI, University of Bordeaux

---

📖 Bibliography

• Duchon et al. "Boltzmann Samplers for the Random Generation of Combinatorial Structures" (2004)
• Sportiello, A. "Improved Boltzmann sampling for the Hadamard product of distributions" (2016)
• Pivoteau, C. "Random generation under Boltzmann model: unlabeled case" (2008)
• Flajolet, P. & Sedgewick, R. "Analytic Combinatorics" (2009)

---

🔍 Future Perspectives

• Extension to labeled combinatorial classes
• Automatic optimization of Poisson parameters
• Applications to bioinformatics and compilation

---

🤝 Contributing

For research collaborations or questions, please contact:

• Nasr-allah HITAR — Nasr-allah.HITAR@Bordeaux-inp.fr
• Philippe DUCHON — philippe.duchon@u-bordeaux.fr