Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

Counting occurrences of 231 in an involution

We study the generating function for the number of involutions on n letters containing exactly r?0 occurrences of 231. It is shown that finding this function for a given r amounts to a routine check of all involutions of length at most 2r+2.     

Generating a Gray Code for P-Sequences

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.     

A new algorithm for generating derangements

A new algorithm for generating derangements based on a well known permutation generation method is presented and analysed. The algorithm is shown to be superior in storage and time requirements to the existing method.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC-A3336.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

On binary reflected Gray codes and functions

The binary reflected Gray code function b is defined as follows: If m is a nonnegative integer, then b(m) is the integer obtained when initial zeros are omitted from the binary reflected Gray code of m.This paper examines this Gray code function and its inverse and gives simple algorithms to generate both. It also simplifies Conder's result that the jth letter of the kth word of the binary reflected Gray code of length n is

     

Gray Code Enumeration of Plane Straight-Line Graphs

We develop Gray code enumeration schemes for geometric straight-line graphs in the plane. The considered graph classes include plane graphs, connected plane graphs, and plane spanning trees. Previous results were restricted to the case where the underlying vertex set is in convex position. Research supported by the FWF Joint Research Project Industrial Geometry S9205-N12 and Projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2005SGR00692.     

Some statistics on Stirling permutations and Stirling derangements

A permutation of the multiset $\{1,1,2,2,\dots ,n,n\}$ is called a Stirling permutation of order $n$ if every entry between the two occurrences of $i$ is greater than $i$ for each $i\in \{1,2,\dots ,n\}$. In this paper, we introduce the definitions of block, even indexed entry, odd indexed entry, Stirling derangement, marked permutation and bicolored increasing binary tree. We first study the joint distribution of ascent plateaux, even indexed entries and left-to-right minima over the set of Stirling permutations of order $n$. We then present an involution on Stirling derangements.     

On Hermitian LCD codes and their Gray image

We provide methods and algorithms to construct Hermitian linear complementary dual (LCD) codes over finite fields. We study existence of self-dual basis with respect to Hermitian inner product, and as an application, we construct Euclidean LCD codes by projecting the Hermitian codes over such a basis. Many optimal quaternary Hermitian and ternary Euclidean LCD codes are obtained. Comparisons with classical constructions are made.     

Combinatorial families that are exponentially far from being listable in Gray code sequence

Let be a collection of subsets of . In this paper we study numerical obstructions to the existence of orderings of for which the cardinalities of successive subsets satisfy congruence conditions. Gray code orders provide an example of such orderings. We say that an ordering of is a Gray code order if successive subsets differ by the adjunction or deletion of a single element of . The cardinalities of successive subsets in a Gray code order must alternate in parity. It follows that if is the difference between the number of elements of having even (resp. odd) cardinality, then is a lower bound for the cardinality of the complement of any subset of which can be listed in Gray code order. For , the collection of -blockfree subsets of is defined to be the set of all subsets of such that if and . We will construct a Gray code order for . In contrast, for we find the precise (positive) exponential growth rate of with as . This implies is far from being listable in Gray code order if is large. Analogous results for other kinds of orderings of subsets of are proved using generalizations of . However, we will show that for all , one can order so that successive elements differ by the adjunction and/or deletion of an integer from . We show that, over an -letter alphabet, the words of length which contain no block of consecutive letters cannot, in general, be listed so that successive words differ by a single letter. However, if and or if and , such a listing is always possible.

     

广义Gray码及其在数字图像置乱中的应用

以图像信息安全问题为背景，讨论了广义Gray码及其在数字图像中的置乱作用，推广了丁玮等人（1999年）的相关结果。给出了图像置乱变换的周期，得到了周期性的一个充分必要条件。     

A Gray code for compositions

The paper describes a rapid algorithm for the sequential listing of the compositions of n into k parts.     

Gray codes for signed involutions

In this paper we present two cyclic Gray codes for signed involutions. The first one has a natural construction, implemented by a CAT algorithm, based in the recursive formula for the number of signed involutions. The second code, although with a higher computational cost, has the smallest possible Hamming distance for this family of objects.     

A Combinatorial construction of the Gray map over Galois rings

In this correspondence, we will introduce a new combinatorial method for a coordinate-wise construction of the homogeneous-weight preserving Gray map for Galois rings by using elementary tools from Affine Geometries. Our construction differs in the methods used from the algebraic constructions done previously in [M. Greferath, S.E. Schmidt, Gray Isometries for finite chain rings and a nonlinear ternary (36, 3¹², 15) code, IEEE Trans. Inform. Theory 45 (1999) 2522-2524; S. Ling, J.T. Blackford, Z_pk+1-linear codes, IEEE Trans. Inform. Theory 48 (2002) 2592-2605].     

股市的灰色预测

本文应用“灰色预测”于股票市场的预测,发现灰色预测在短期预测中富有很高的效率。     

A random construction for permutation codes and the covering radius

We analyse a probabilistic argument that gives a semi-random construction for a permutation code on n symbols with distance n − s and size Θ(s!(log n)^1/2), and a bound on the covering radius for sets of permutations in terms of a certain frequency parameter.      

On the Gray index conjecture for phantom maps

We study the Gray index, a numerical invariant for phantom maps. It has been conjectured that the only phantom map between finite-type spaces with infinite Gray index is the constant map. We disprove this conjecture by constructing a counter example. We also prove that this conjecture is valid if the target spaces of the phantom maps are restricted to being simply connected finite complexes.As a result of the counter example, we can show that SNT^∞(X) can be non-trivial for some space X of finite type.