39 citations · 46 across the 8 of their papers we have counts for
10 papers
Leap generators for composition schemes
Éric Fusy, Carine Pivoteau
Leap generators have been introduced in [Duchon et al.'04] for exact-size random generation of structures in a class of the form (sequence c…
Effective Asymptotics of Combinatorial Systems
Carine Pivoteau, Bruno Salvy
Analytic combinatorics studies asymptotic properties of families of combinatorial objects using complex analysis on their generating functions. In their reference book on the subje…
Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms
Cyril Nicaud, Carine Pivoteau, Stéphane Vialette
We analyze the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms through the lens of computer architecture, investigating the impact of incorporating a simp…
Record-biased permutations and their permuton limit
Mathilde Bouvel, Cyril Nicaud, Carine Pivoteau
In this article, we study a non-uniform distribution on permutations biased by their number of records that we call \emph{record-biased permutations}. We give several generative pr…
On the Worst-Case Complexity of TimSort
Nicolas Auger, Vincent Jugé, Cyril Nicaud +1
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two…
Analysis of Algorithms for Permutations Biased by Their Number of Records
Nicolas Auger, Mathilde Bouvel, Cyril Nicaud +1
The topic of the article is the parametric study of the complexity of algorithms on arrays of pairwise distinct integers. We introduce a model that takes into account the non-unifo…
An algorithm computing combinatorial specifications of permutation classes
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +2
This article presents a methodology that automatically derives a combinatorial specification for a permutation class C, given its basis B of excluded patterns and the set of simple…
Combinatorial specification of permutation classes
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +2
This article presents a methodology that automatically derives a combinatorial specification for the permutation class C = Av(B), given its basis B of excluded patterns and the set…
Algorithms for Combinatorial Systems: Well-Founded Systems and Newton Iterations
Carine Pivoteau, Bruno Salvy, Michele Soria
We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing nume…
Random sampling of plane partitions
Olivier Bodini, Eric Fusy, Carine Pivoteau
This article presents uniform random generators of plane partitions according to the size (the number of cubes in the 3D interpretation). Combining a bijection of Pak with the meth…