Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: generating trees

Sortuj według:

Ogranicz wyniki do:

A Generating Tree for Permutations Avoiding the Pattern 122+3

Duchi E., Guerrini V., Rinaldi S.

Fundamenta Informaticae

2018

Vol. 163, nr 1

21--39

In this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 1 23 4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build every object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 1 23 4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation.

Pattern 1^j+10^j Avoiding Binary Words

Bilotta S., Merlini D., Pergola E., Pinzani R.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

35-55

In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^j=10^j By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.

On Generating All Binary Trees

Skarbek W.

Fundamenta Informaticae

2007

Vol. 75, nr 1-4

505-536

In context of Pawlak's machine a general iterative meta scheme for generating of combinatorial objects is introduced and applied to proof the correctness of ASR (Arm Switching and Rotation) algorithm generating all binary trees on k nodes. The average time complexity of the ASR algorithm and B* are analyzed and compared to the B algorithm discussed by Knuth. The analyzed algorithms are all obtained by various natural correspondences from author's DCP (Degrade and Compress Path) algorithm for generating all ordered trees on k+1 nodes.