Restricted compositions and permutations: From old to new Gray codes

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let ? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of ? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that ? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so ? put under a single roof all these Gray codes.As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems.     

Whole mirror duplication-random loss model and pattern avoiding permutations

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 p²+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) [10]. Other relative models are also considered.     

Efficient generation of the ideals of a poset in Gray code order

Preusse and Ruskey [G. Pruesse, F. Ruskey, Gray codes from antimatroids, Order 10 (1993) 239-252] presented an algorithm for generating a Gray code for the ideals of a poset, where two adjacent ideals differ by one or two elements. Their algorithm takes O(n) amortized time per ideal. Squire [M. Squire, Enumerating the ideals of a poset, http://citeseer.ist.psu.edu/465417.html] presented a recurrence for the ideals of a poset that enabled him to find an algorithm for generating these ideals in O(logn) amortized time per ideal, but not in Gray code order. We use Squire's recurrence to find a Gray code for the ideals of a poset, where two adjacent ideals differ by one or two elements. In the worst case our algorithm has the same complexity as that of Pruesse and Ruskey and in the other cases its complexity is better and approaches that of Squire's algorithm.     

Loop-free Gray code algorithm for the e-restricted growth functions

The subject of Gray codes algorithms for the set partitions of {1,2,…,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of Knuth?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,…,n}, Ruskey and Savage (1994) [9] generalized Ehrlich?s results and give two Gray codes for the set of partitions of {1,2,…,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques.In this paper, we introduce the set of e-restricted growth functions (a generalization of restricted growth functions) and extend the aforementioned results by giving a Gray code with distance one for this set; and as a particular case we obtain a new Gray code for set partitions in restricted growth function representation. Our Gray code satisfies some prefix properties and can be implemented by a loop-free generating algorithm using classical techniques; such algorithms can be used as a practical solution of some difficult problems. Finally, we give some enumerative results concerning the restricted growth functions of order d.     

More restrictive Gray codes for necklaces and Lyndon words

In the last years, the order induced by the Binary Reflected Gray Code or its generalizations shown an increasing interest. In this note we show that the BRGC order induces a cyclic 2-Gray code on the set of binary necklaces and Lyndon words and a cyclic 3-Gray code on the unordered counterparts. This is an improvement and a generalization to unlabeled words of the result in [V. Vajnovszki, Gray code order for Lyndon words, Discrete Math. Theoret. Comput. Sci. 9 (2) (2007) 145-152; M. Weston, V. Vajnovszki, Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications/Algebra and Theoretical Computer Science, in press]; however an algorithmic implementation of our Gray codes remains an open problem.     

A general exhaustive generation algorithm for Gray structures

Starting from a succession rule for Catalan numbers, we define a procedure for encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only by one digit. The Gray code we obtain can be generalized to all the succession rules with the stability property: each label (k) has in its productions two labels c ₁ and c ₂, always in the same position, regardless of k. Because of this link, we define Gray structures as the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, such as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of Walsh’s one, working in O(1) worst-case time per word for generating Gray codes.     

On level-weight studies of binary and m-ary gray codes

Gray codes are useful in the minimization of digital errors due to an ambiguous analog signal between two adjacent levels. The weight structure in coding has its own significance. In this paper, we study the weight structure of the binary Gray code G_n⁽⁰⁾ and extend the result for nonbinary Gray codes G_m:n⁽⁰⁾. With our study it is possible to find the weight of a codeword occupying a given place in the codebook.     

Enumerating submultisets of multisets

We consider the problem of enumerating the submultisets of a multiset, in which each element has equal multiplicity. The crucial property is that consecutive submultisets in this listing differ one in the cardinality of exactly one of the elements. This is a generalization to k-ary numbers of the so-called Gray Codes for binary numbers. The result is not new, but we think the proof is.We give an example how these results were used during our research into switching classes. Finally, we indicate how the method can be generalized to arbitrary multisets.     

Exhaustive generation of combinatorial objects by ECO

The problem of exhaustively generating combinatorial objects can currently be applied to many disciplines, such as biology, chemistry, medicine and computer science. A well known approach to the exhaustive generation problem is given by the Gray code scheme for listing n-bit binary numbers in such a way that successive numbers differ in exactly one bit position. In this work, we introduce an exhaustive generation algorithm, which is general for the classes of succession rules considered in [1]. We also show that our algorithm is efficient in an amortized sense; it actually uses only a constant amount of computation per object.Received: 10 October 2003, Revised: 10 February 2004, Published online: 21 April 2004     

Towards understanding optimal MIMD queueless routing of arbitrary permutations on hypercubes

This paper addresses the problem of the offline routing of arbitrary permutations on hypercubes under the MIMD queueless communication constraints which imposes that only one message can be located in each node of the hypercube right through the routing. According to e-cube routing, this kind of communication may require in the worst cases at least n exchanges steps on an n-dimensional hypercube. It has been conjectured that in the general case n steps suffice. The conjecture has been proved either by enumeration or by program for the particular cases of n??3. We revisit the problem through the k-partitioning paradigm based on maximum matching of bipartite graphs concept to take advantage of the recursive structure of the hypercube topology. The paradigm consists in looking for each message a transition node distant of at most say k<n hops from its current node such that all the messages can be routed to their transition nodes in k hops then finally routed to their final destination nodes in n?k hops on two disjoints hypercubes. In others words, the paradigm consists to determine an upstream permutation routable in k steps and which leads to two independent downstream permutations routable in n?k steps on two disjoint hypercubes. With this purpose, we give a characterization of the non-1-partitionable permutations from which the proof of the conjecture comes straightforwardly for n??2 and the non-1-partitionable permutations can be built whatever n may be. For n=3, we thus confirm the existence of exactly three classes of non-1-partitionable permutations and prove that there are two classes of upstream permutations to avoid when 2-partitioning any non-1-partitionable permutation. The process to avoid such upstream permutations is presented, and leads to a formal proof of the conjecture for n=3. For n>3, experiences gained in routing permutations on 4D-hypercubes allow conjecturing that in these cases, too, any non-1-partitionable permutation is 2-partitionable. Indeed, the analysis carried out for the 3D-hypercubes is repeatable to identify, certainly more laboriously given their combinatory, the upstream permutations to avoid when 2-partitioning a non-1-partitionable permutation on a 4D-hypercube. The proof that resulting downstream permutations on a 3D-hypercube can be routed in 2 steps is a consequence of the fact that for n=2 and 3 any permutation on a nD-hypercube can be routed in n steps.     

Routing Permutations on Hypercube Machines with Half-Duplex Links

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω⁻¹ in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

Synthetic Sequence Design for Signal Location Search

We present a new approach to identify the locations of critical DNA or RNA sequence signals which couples large-scale synthesis with sophisticated designs employing combinatorial group testing and balanced Gray codes. Experiments in polio and adenovirus demonstrate the efficiency and generality of this procedure. In this paper, we give a new class of consecutive positive group testing designs, which offer a better tradeoff of cost, resolution, and robustness than previous designs for signal search. Let n denote the number of distinct regions in a sequence, and d the maximum number of consecutive positives regions which can occur. We propose a design which improves on the consecutive-positive group testing designs of Colbourn. Our design completely identifies the boundaries of the positive region using t tests, where t≈log₂(1.27n/d)+0.5log₂(log₂(1.5n/d))+d.     

Data Rearrangement between Radix-k and Lee Distance Gray Codes in k-ary n-cubes

The k-ary n-cube is one of the popular topologies for interconnecting processors in multicomputers. This paper studies the difference in communication requirements between two Lee distance Gray codes when moving data from processors in normal radix k order to those in Gray code order in k -ary n-cube networks. Algorithms for k-ary to Gray code conversion, and vice versa, in k-ary n-cube networks are described under various channel constraints, i.e., one-port and all-port communication assumptions. The minimum length path routing algorithm for nonreflective Gray code requires roughly M(k/4) and (n−1) M(k/4) steps for data element transfers under all-port communication and one-port communication, respectively, for M elements per node. It is also shown that using a nonminimum length path routing algorithm, the number of steps for data element transfers can be halved. Lower bounds for the number of element transfers are derived, and the proposed algorithm using nonminimum length paths under one-port communication is shown to be near optimal.     

Translation sets of permutations: Enumeration of selfcomplementary step-cycles

For given integern>2, there corresponds to each step-cycle a set of permutations, called a translation set. All the translation sets of permutations on the setS={1, 2, ...,n?1} form a set of equivalence classes on the set of all permutations onS. The selfcomplementary step-cycles are described and enumerated. A more general introduction to translation sets may be found in [4] and [3].     

Shorthand Universal Cycles for Permutations

The set of permutations of ??n??={1,??,n} in one-line notation is ??(n). The shorthand encoding of a ₁?a _n ????(n) is a ₁?a _n?1. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n?1 are the shorthand encodings of ??(n). When an SP-cycle is decoded, the order of ??(n) is a Gray code in which successive permutations differ by the prefix-rotation ?? _i =(1 2 ? i) for i??{n?1,n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum ??weight?? (number of ?? _n?1s in the Gray code). An SP-cycle n a n b?n z is ??periodic?? if its ??sub-permutations?? a,b,??,z equal ??(n?1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the (n?1)-permutohedron. We provide two constructions: B(n) and C(n). In B(n) the spanning trees use ??half-hunts?? from bell-ringing, and in C(n) the sub-permutations use cool-lex order by Williams (SODA, 987?C996, 2009). Algorithmic results are: (1)?memoryless decoding of B(n) and C(n), (2)?O((n?1)!)-time generation of B(n) and C(n) using sub-permutations, (3)?loopless generation of B(n)??s binary representation n bits at a time, and (4)?O(n+??(n))-time ranking of B(n)??s permutations where ??(n) is the cost of computing a permutation??s inversion vector. Results (1)?C(4) improve on those for the previous SP-cycle construction D(n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art.?45, 2010), which we characterize here using ??recycling??.     

Random Data Accesses on a Coarse-Grained Parallel Machine I. One-to-One Mappings

This paper describes deterministic communication-efficient algorithms for performing dynamic permutations on a coarse-grained parallel machine. Our analysis shows that the general permutation operation can be completed inCμn/p(+ lower order terms) time and is optimal and scalable providedn⪢p³+p²τ/μ (nis the size of the permutation or the number of elements distributed across thepprocessors, τ is the start-up overhead, and 1/μ is the data transfer rate).Cis a small constant typically between 2 and 3 for write permutations, slightly higher for read permutations. Modifications to exploit locality of access are presented. Special classes of permutations that are optimal for smaller sizes are also described. A companion paper [22] deals with the problem of random data accesses with hot spots.     

An algorithm for computation of translation invariant groups and the subgroup lattice

For given integern>2 the translation sets of permutations on 1, 2, ...,n?1 form a set of equivalence classes on the symmetric group ? _n-1. To each translation set there corresponds one step-cycle. A group consisting of a union of disjoint translation sets is called a translation invariant group. In this paper, we want to describe an algorithm for a systematic search for all translation invariant groups in ? _n-1.     

More on permutation generation methods

We study a class of recursive permutation generation methods which construct a sequence of alln! permutations ofn elements by repeatedly generating all permutations of the elements in the firstn?1 positions and exchanging one of them with the element in then-th position. We give a general principle which enables us to obtain a whole class of permutation generation methods. This class includes the well-known algorithms of Wells and Heap as special cases, but contains also many new simple algorithms. Moreover, we are able to produce permutation generation methods with prescribed properties concerning the change that should be made in order to skip a block ofm! permutations with fixed elements in positionsm+1, …,n. For any method in our class, this change is a single transposition for any oddm>1, and a cyclic shift along a cycle of lengthm for any evenm.