*Journal of
Information and Optimization Science ***Generating binary
trees in A-order from codewords defined on a four-letter alphabet**

Vincent Vajnovszki and Jean Pallo

We use two recent
codings of binary trees by words over a four-letter alphabet in order
to generate binary trees in A-order. Rankimg and unranking algorithms
are also discussed.

*Bulletin of the
European Association for Theoretical Computer Science ***Constant
time generation of binary unordered trees**

Vincent Vajnovszki

We present an optimal coding for binary unordered trees and
exhibit a generating algorithm with a constant average complexity and
the associated rank and unrank algorithms

*Studies in
Informatics and Control* **Constant Time Algorithm for
Generating Binary Trees Gray Codes **

Vincent Vajnovszki

Frank
Ruskey and Andrzej Proskurowski (1990) gave a recursive algorithm for
generating binary trees as represented by bitstrings with a given
prefix, such that successive bitstrings differ by the transposition
of two bits and the concatenation of generated lists forms a Gray
code. This paper presents a new Gray code for the set of all such
bitstrings and an algorithm for directly generating binary trees
represented by Zaks sequences.

*9th
International Conference on Parallel and Distributed Computing
Systems - ISCA* **Two Optimal Parallel Algorithms for
Generating P-sequences **

Vincent Vajnovszki and Chris Phillips

We propose two cost-optimal parallel algorithms for
generating binary ordered trees represented by P-sequences. The first
algorithm is adaptive and executes according to an *SPMD*
parallel model. Processors execute the same algorithm independently
without synchronised access to shared memory/communication. The
second algorithm also executes according to an *SPMD* model, but
two or more processors are allowed to read simultaneously from the
same (shared) memory location, but any write is synchronised (a *CREW*
model), and generates all P-sequences in lexicographic order.

*Gascom 96, Caen
30 jan.- 1 fev. 1997* **Génération aléatoire
des arbres binaires par des algorithmes de rang inverse**

Vincent
Vajnovszki

L'objet de cet article est de passer en revue
quelques algorithmes efficaces de rang inverse pour différents
codages d'arbres binaires et différents ordres sur ces arbres.
Avec un générateur de nombres aléatoires tous
ces algorithmes sont facilement transposables en des algorithmes de
génération aléatoire pour les arbres binaires.
Les même algorithmes de rang peuvent servir à la
génération quasi-aléatoire d'un échantillonnage
de taille *k* : on tire aléatoirement un entier dans un
certain intervalle, on lui applique l'algorithme de rang inverse,
puis on calcule *k-1* fois la fonction successeur (qui dans la
plupart des cas ont une complexité en *O(1)*).

*12th
International Conference on Computers and Their Applications - ISCA
***Optimal Parallel Algorithm for Generating k-ary
Trees**

Vincent Vajnovszki and Chris Phillips

The only published algorithm for generating

*Journal of
Information and Optimization Science* **Ranking and Unranking
k-ary Trees with a 4k-4 Letter Alphabet**

Vincent Vajnovszki and Jean Pallo

The problem of the direct generation in A-order of binary trees was stated by Zaks in 1980. In 1988 Roelants van Baronaigien and Ruskey gave a solution for

*Parallel
Processing Letters* **Parallel algorithms for generating
well-formed parentheses strings**

Vincent Vajnovszki and Jean
Pallo

We present two cost-optimal parallel algorithms
generating the set of all well-formed parentheses strings of length
*2n* with constant delay for each generated string. In our first
algorithm we generate in lexicographic order well-formed parentheses
strings represented by bitstrings, and in the second one we use the
representation by weight sequences. In both cases the computational
model is based on an architecture *CREW PRAM*, where each
processor performs the same algorithm simultaneously on a different
set of data. Different processors can access the shared memory at the
same time to read different data in the same or different memory
locations, but no two processors are allowed to write into the same
memory location simultaneously. These results complete a recent
parallel generating algorithm for well-formed parentheses strings in
a linear array of processors model presented by Akl and Stojmenovic
in 1996.

*International
Conference on Computer Applications in Industry and Engineering,
1998, Las Vegas, Nevada, U.S.A.* **Parallel Generation of
Nondecreasing Paths and Applications**

Vincent Vajnovszki

We
introduce a unified approach for a class of parallel generating
algorithms for combinatorial objects by presenting a generic
algorithm which generates increasing paths with some restrictions
and, as a particular case, it produces combinations, compositions of
an integer, binary and *k*-ary trees. Our algorithm is targeted
at a linear array of processors model, and satisfies some strong
optimality criteria.

*Information
Processing Letters* **On the Loopless Generation of Binary
Tree Sequences **

Vincent Vajnovszki

Weight sequences
were introduced by Pallo in 1986 for coding binary trees and he
presented a constant amortized time algorithm for their generation in
lexicographic order. A year later, Roelants van Baronaigien and
Ruskey developed a recursive constant amortized time algorithm for
generating Gray code for binary trees in Pallo's representation. It
is common practice to find a loopless generating algorithm for a
combinatorial object when enunciating a Gray code for this object. In
this paper we regard weight sequences as variations and apply a
Williamson algorithm in order to obtain a loopless generating
algorithm for the Roelants van Baronaigien and Ruskey's Gray code for
weight sequences.

*GASCOM '99*
**Gray code for P-Sequences **

Vincent Vajnovszki

P-sequences are used for coding binary trees and they are
also a *concise* representation for well-formed parenthesis
strings. We present a Gray code and a loopless generating algorithm
for P-sequences, and derive them in a Gray code and a loopless
generating algorithm for well-formed parenthesis strings.

*Parallel
Processing Letters* **Systolic Generation of k-ary
trees**

Vincent Vajnovszki and Chris Phillips

The only parallel generating algorithms for

*International
Journal of Mathematical Algorithms* **Generating a Gray Code
for P-sequences**

Vincent Vajnovszki

P-sequences are
used for coding binary trees and they are also an alternative
representation for well-formed parentheses strings. We present here
the first Gray code and loopless generating algorithm for
P-sequences, and extend them in a Gray code and a new loopless
generating algorithm for well-formed parentheses strings. Ranking and
unranking algorithms are also discussed.

*Discrete
Mathematics and Theoretical Computer Science* **A loopless
generation of bitstrings without p consecutive ones**

Vincent Vajnovszki

Let

*Journal of
Information and Optimization Science* **On the Reconstruction
of a Motzkin Tree from its Code**

Ronny Pattisina and Vincent
Vajnovszki

Often in computer science combinatorial objects
with geometrical significance are represented concisely, as words
over a given alphabet. In this paper we present an efficient, simple
to understand and simple to implement algorithm which permits the
construction of Motzkin trees (*1-2* trees) from their linear
(word) representation.

*Acta Informatica*
**Gray visiting Motzkins**

Vincent Vajnovszki

We
present the first Gray code for Motzkin words and their
generalizations: *k* colored Motzkin words and Schroder words.
The construction of these Gray codes is based on the observation that
a *k* colored Motzkin word is the *shuffle* of a Dyck word
by a *k*-ary variation on a trajectory which is a combination.
In the final part of the paper we give some algorithmic
considerations and other possible applications of the techniques
introduced here.

*Theoretical
Computer Science*, **A Loopless Algorithm for Generating the
Permutations of a Multiset**

Vincent Vajnovszki

Many
combinatorial structures can be constructed from simpler components.
For example, a permutation can be constructed from cycles, or a
Motzkin word from a Dyck word and a combination. In this paper we
present a constructor for combinatorial structures, called *shuffle
on trajectories* (defined previously in a non-combinatorial
context), and we show how this constructor enables us to obtain a new
loopless generating algorithm for multiset permutations from similar
results for simpler objects.

*Discrete
Applied Mathematics*, **Gray Code for Derangements**

Jean-Luc Baril, Vincent Vajnovszki

We give the first Gray
code and constant average time generating algorithm for *derangements
*, i.e., permutations with no fixed points. In our Gray code, each
derangement is transformed into its successor either via one or two
transpositions or a rotation of three elements. We generalize these
results to permutations with number of fixed points bounded between
two constants.

*WORDS03*,
**Gray codes for order p Lucas strings**

Jean-Luc Baril, Vincent Vajnovszki

We give the first Gray code for the set of order

*JMITL04*, **Gray
viziting Lyndons**

Vincent Vajnovszki

In this paper we
show that a slight modification of the original Gray code order
induces a Gray code on the set of length *n* binary
pre-necklaces, necklaces, bracelets and Lyndon words. Given the
simplicity of our approach is surprising that it was never explored.

*GASCom*,
**Gray codes for necklaces and Lyndon words of arbitrary base**

M.
Weston, V. Vajnovszki

Recently, a Gray code for unrestricted
binary necklaces and their relatives was discovered by Vajnovszki
[Discrete Mathematics & Theoretical Computer Science, to appear].
The Gray code is constructed by modifying the classical FKM algorithm
for generating necklaces in lexicographic order. We present a
generalisation of Vajnovszki's algorithm, giving a Gray code for
necklaces and their relatives over an arbitrarily-large alphabet.
Each string in the resulting code differs from adjacent strings in at
most three positions. To our knowledge this is the first Gray code
for necklaces of arbitrary base.

*CGCS2007*,
**Generating involution, Bell and Stirling permutations**

I.
Fanti, M. Poneti and V. Vajnovszki

There is a wide literature
on the exhaustive generation of permutations, beginning by the
campanologists' historical works followed by more systematical
approaches. More recently, a great interest was given to the
generation of particular classes of permutations: involutions,
derangements, with fixed number of cycles or inversions, with
forbidden patterns ... In this paper we give a new generating
algorithm for unrestricted permutations. It is based on both, the
decomposition of a permutation as product of transpositions and a
product of disjoint cycles. We show that slight modifications of our
general algorithm produce similar algorithms for some restricted
classes of permutations: involutions or Bell permutations. Further
refinement yelds algorithms for these classes of permutations subject
to other restrictions: given number of cycles or fixed points ...

*TCJ*, **Some Generalizations of a Simion-Schmidt
Bijection**

A. Juarna, V. Vajnovszki

In 1985 Simion and
Schmidt gave a constructive bijection $\varphi$ from the set of all
length *(n-1)* binary strings having no two consecutive 1s to
the set of all length *n* permutations avoiding all patterns in
*123,132,213*. In this paper we generalize $\varphi$ to an
injective function from *{0,1}^{n-1}* to the set *S_n* of
all length *n* permutations and derive from it four bijections
$\varphi: P\to Q$ where $P\subseteq \{0,1\}^{n-1}$ and $Q\subset
S_n$. The domains are sets of restricted binary strings and the
codomains are sets of pattern-avoiding permutations. As a particular
case we retrieve the original Simion-Schmidt bijection.