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 k-ary trees in parallel is that of Akl and Stojmenovic in 1996. The trees are represented by an inversion table and the processor model is a multicomputer linear array. In this paper we present a parallel generating algorithm for k-ary trees represented by bitstrings for execution on a shared memory multiprocessor.

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 k-ary trees with n internal nodes using an encoding sequences of kn+1 integers between 1 and n. Vajnovszki and Pallo improved this result for binary trees in 1994 using words of length n-1 on a four letter alphabet. Recently Korsh generalized the Vajnovszki and Pallo's generating algorithm to k-ary trees using an alphabet whose the cardinality depends on k but not on n. We give in this paper ranking and unranking algorithms for k-ary trees using the Korsh's encoding scheme.

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 k-ary trees are those of Akl and Stojmenovic in 1996 and of Vajnovszki and Phillips in 1997. In the first of them trees are represented by an inversion table and the processor model is a linear array multicomputer. In the second trees are represented by bitstrings and the algorithm executes on a shared memory multiprocessor. In this paper we present a parallel generating algorithm for k-ary trees represented by P-sequences for execution on a linear array multicomputer.

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 F_n ^(p) be the set of all n-length bitstrings such that there are no p consecutive 1s. F_n ^(p) is counted with the pth order Fibonacci numbers and it may be regarded as the subsets of {1,2, ...,n} without p consecutive elements and bitstrings in F_n ^(p) code a particular class of trees or compositions of an integer. In this paper we give a Gray code for F_n ^(p) which can be implemented in a recursive generating algorithm, and finally in a loopless generating algorithm.

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 p length-n Lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1^l prefix and a 1^m suffix with l+m>=p. Our Gray code proves also that the order p n-dimensional Lucas cube is Hamiltonian iff n is not a multiple of p+1, and its second power is always Hamiltonian.

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.