Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a Greedy Algorithm to Construct Universal Cycles for Permutations
153
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A universal cycle for permutations of length $n$ is a cyclic word or permutation, any factor of which is order-isomorphic to exactly one permutation of length $n$, and containing all permutations of length $n$ as factors. It is well known that universal cycles for permutations of length $n$ exist. However, all known ways to construct such cycles are rather complicated. For example, in the original paper establishing the existence of the universal cycles, constructing such a cycle involves finding an Eulerian cycle in a certain graph and then dealing with partially ordered sets. In this paper, we offer a simple way to generate a universal cycle for permutations of length $n$, which is based on applying a greedy algorithm to a permutation of length $n-1$. We prove that this approach gives a unique universal cycle $Pi_n$ for permutations, and we study properties of $Pi_n$.
rate research
Read More
Recursive permutations whose cycles are the classes of a decidable equivalence relation are studied; the set of these permutations is called $mathrm{Perm}$, the group of all recursive permutations $mathcal{G}$. Multiple equivalent computable representations of decidable equivalence relations are provided. $mathcal{G}$-conjugacy in $mathrm{Perm}$ is characterised by computable isomorphy of cycle equivalence relations. This result parallels the equivalence of cycle type equality and conjugacy in the full symmetric group of the natural numbers. Conditions are presented for a permutation $f in mathcal{G}$ to be in $mathrm{Perm}$ and for a decidable equivalence relation to appear as the cycle relation of a member of $mathcal{G}$. In particular, two normal forms for the cycle structure of permutations are defined and it is shown that conjugacy to a permutation in the first normal form is equivalent to membership in $mathrm{Perm}$. $mathrm{Perm}$ is further characterised as the set of maximal permutations in a family of preordered subsets of automorphism groups of decidable equivalences. Conjugacy to a permutation in the second normal form corresponds to decidable cycles plus decidable cycle finiteness problem. Cycle decidability and cycle finiteness are both shown to have the maximal one-one degree of the Halting Problem. Cycle finiteness is used to prove that conjugacy in $mathrm{Perm}$ cannot be decided and that it is impossible to compute cycle deciders for products of members of $mathrm{Perm}$ and finitary permutations. It is also shown that $mathrm{Perm}$ is not recursively enumerable and that it is not a group.
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian, this baseline result is used as the basis of existence proofs for universal cycles (also known as generalized deBruijn cycles or U-cycles) of several combinatorial objects. We extend the body of known results by presenting new results on the existence of universal cycles of monotone, augmented onto, and Lipschitz functions in addition to universal cycles of certain types of lattice paths and random walks.
There is a bijection from Schroder paths to {4132, 4231}-avoiding permutations due to Bandlow, Egge, and Killpatrick that sends area to inversion number. Here we give a concise description of this bijection.
We compute the limiting distribution, as n approaches infinity, of the number of cycles of length between gamma n and delta n in a permutation of [n] chosen uniformly at random, for constants gamma, delta such that 1/(k+1) <= gamma < delta <= 1/k for some integer k. This distribution is supported on {0, 1, ... k} and has 0th, 1st, ..., kth moments equal to those of a Poisson distribution with parameter log (delta/gamma). For more general choices of gamma, delta we show that such a limiting distribution exists, which can be given explicitly in terms of certain integrals over intersections of hypercubes with half-spaces; these integrals are analytically intractable but a recurrence specifying them can be given. The results herein provide a basis of comparison for similar statistics on restricted classes of permutations.
Concurrency has been a subject of study for more than 50 years. Still, many developers struggle to adapt their sequential code to be accessed concurrently. This need has pushed for generic solutions and specific concurrent data structures. Wait-free universal constructs are attractive as they can turn a sequential implementation of any object into an equivalent, yet concurrent and wait-free, implementation. While highly relevant from a research perspective, these techniques are of limited practical use when the underlying object or data structure is sizable. The copy operation can consume much of the CPUs resources and significantly degrade performance. To overcome this limitation, we have designed CX, a multi-instance-based wait-free universal construct that substantially reduces the amount of copy operations. The construct maintains a bounded number of instances of the object that can potentially be brought up to date. We applied CX to several sequential implementations of data structures, including STL implementations, and compared them with existing wait-free constructs. Our evaluation shows that CX performs significantly better in most experiments, and can even rival with hand-written lock-free and wait-free data structures, simultaneously providing wait-free progress, safe memory reclamation and high reader scalability.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
