Search results for "Permutation"
showing 10 items of 132 documents
Unfolding of saddle-nodes and their Dulac time
2016
Altres ajuts: UNAB10-4E-378, co-funded by ERDF "A way to build Europe" and by the French ANR-11-BS01-0009 STAAVF. In this paper we study unfoldings of saddle-nodes and their Dulac time. By unfolding a saddle-node, saddles and nodes appear. In the first result (Theorem A) we give a uniform asymptotic expansion of the trajectories arriving at the node. Uniformity is with respect to all parameters including the unfolding parameter bringing the node to a saddle-node and a parameter belonging to a space of functions. In the second part, we apply this first result for proving a regularity result (Theorem B) on the Dulac time (time of Dulac map) of an unfolding of a saddle-node. This result is a b…
Whole mirror duplication-random loss model and pattern avoiding permutations
2010
International audience; In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p of duplications of the identity is the class of permutations avoiding the alternating permutations of length p2+1. We also compute the number of duplications necessary and sufficient to obtain any permutation of length n. We provide two efficient algorithms to reconstitute a possible scenario of whole mirror duplications from identity to any permutation of length n. One of them uses the well-known binary reflected Gray code (Gray, 1953). Other relative mo…
Gray code for Cayley permutations
2003
A length-n Cayley permutation p of a total ordered set S is a length-n sequence of elements from S, subject to the condition that if an element x appears in p then all elements y < x also appear in p . In this paper, we give a Gray code list for the set of length-n Cayley permutations. Two successive permutations in this list differ at most in two positions.
Gray code for compositions of n with parts 1 and p
2009
International audience
ECO-generation for some restricted classes of compositions
2013
International audience; We study several restricted classes of compositions by giving one-to-one maps between them and different classes of restricted binary strings or pattern avoiding permutations. Inspired by the ECO method, new succession rules for these classes are presented. Finally, we obtain generating algorithms in Constant Amortized Time (CAT) for theses classes.
Etudes d'objets combinatoires : applications à la bio-informatique
2011
This thesis considers classes of combinatorial objects that model data in bioinformatics. We have studied two methods of mutation of genes within the genome : duplication and inversion. At first,we study the problem of the whole mirror duplication-random lossmodel in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this method after p duplications from the identity is the class of permutations avoiding alternating permutations of length 2p + 1.We also enumerate the number of duplications that are necessary and sufficient to obtain any permutation of length n from the identity. We also suggest two efficient algorithms to reconstruct two different …
Darbu plānošanas optimizācijas problēmu risināšana ar binārās programmēšanas metodēm
2016
Darbā aprakstītas trīs dažādas flow shop problēmas ar uzdevumu minimizēt kopējo darbu izpildes laiku: permutation flow shop problēma, blocking flow shop problēma un no-wait flow shop problēma. Katrai no problēmām ir atrasts atbilstošais lineārās programmēšanas uzdevums ar veseliem un bināriem mainīgajiem. Problēmu risināšanai ir aprobētas divas klasiskās metodes, ko izmando diskrētās programmēšanas uzdevumiem: Gomorī apgriešanas metode un sazarošanās un robežu algoritms. Skaitliskie aprēķini tika veikti, izmantojot datorprogrammu LPSolve IDE.
On Prefix Normal Words
2011
We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length $k$, no factor of length $k$ has more $a$'s than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contai…
Alignments of Time Intensity curves in sensory analysis
2006
International audience
Permutations of zero-sumsets in a finite vector space
2020
Abstract In this paper, we consider a finite-dimensional vector space 𝒫 {{\mathcal{P}}} over the Galois field GF ( p ) {\operatorname{GF}(p)} , with p being an odd prime, and the family ℬ k x {{\mathcal{B}}_{k}^{x}} of all k-sets of elements of 𝒫 {\mathcal{P}} summing up to a given element x. The main result of the paper is the characterization, for x = 0 {x=0} , of the permutations of 𝒫 {\mathcal{P}} inducing permutations of ℬ k 0 {{\mathcal{B}}_{k}^{0}} as the invertible linear mappings of the vector space 𝒫 {\mathcal{P}} if p does not divide k, and as the invertible affinities of the affine space 𝒫 {\mathcal{P}} if p divides k. The same question is answered also in the case where …