TITLE

A New Universal Cycle for Permutations

AUTHOR(S)
Wong, Dennis
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1393
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We introduce a novel notation, the relaxed shorthand notation, to encode permutations. We then present a simple shift rule that exhaustively lists out each of the permutations exactly once. The shift rule induces a cyclic Gray code for permutations where successive strings differ by a rotation or a shift. By concatenating the first symbol of each string in the listing, we produce a universal cycle for permutations in relaxed shorthand notation. We also prove that the universal cycle can be constructed in O(1)-amortized time per symbol using O( n) space.
ACCESSION #
126308044

 

Related Articles

  • ADDRESS SEQUENCES AND BACKGROUNDS WITH DIFFERENT HAMMING DISTANCES FOR MULTIPLE RUN MARCH TESTS. YARMOLIK, SVETLANA // International Journal of Applied Mathematics & Computer Science;Sep2008, Vol. 18 Issue 3, p329 

    It is widely known that pattern sensitive faults are the most difficult faults to detect during the RAM testing process. One of the techniques which can be used for effective detection of this kind of faults is the multi-background test technique. According to this technique, multiple-run memory...

  • Shape and Color Comprehensive Reconstruction Technology. Wu haibin; Sun xiaoming; Yu xiaoyang; Liu chao; Yu shuchun // International Journal of Signal Processing, Image Processing & P;2014, Vol. 7 Issue 3, p83 

    The article presents a study which addresses improve accuracy of shape reconstruction and authenticity of color reconstruction. The elimination of decoding error and quantization error in order to improve accuracy of shape reconstruction is mentioned. Also, analyzing the coupling phenomena of...

  • Projector Calibration Method using Orthogonal Gray Code Combined with Trapezoid Phase Shift Code. Yu Xiaoyang; Meng Xiaoliang; Wu Haibin; Zang Tianjian; Xiao Zhenyu // International Journal of Multimedia & Ubiquitous Engineering;2014, Vol. 9 Issue 10, p1 

    In coded-structured light three dimensional measurement system, system calibration plays an important role for the measurement accuracy. Projector calibration is an important part of the system calibration. Therefore, this paper proposes a projector calibration method with simple calibration...

  • Most Significant Bit.  // Network Dictionary;2007, p317 

    A definition of the term "Most Significant Bit" (MSB) is presented. MSB refers to the bit n-1 in an n bit binary number, the bit with the greatest weight. It is also the first or leftmost bit when the number is written in the usual way.

  • QUATERNARY PERIODIC COMPLEMENTARY/Z-COMPLEMENTARY SEQUENCE SETS BASED ON INTERLEAVING TECHNIQUE AND GRAY MAPPING. Fanxin Zeng; Xiaoping Zeng; Zhenyu Zhang; Guixin Xuan // Advances in Mathematics of Communications;May2012, Vol. 6 Issue 2, p237 

    A family of quaternary periodic complementary sequence (PCS) or Z-complementary sequence (PZCS) sets is presented. By combining an interleaving technique and the inverse Gray mapping, the proposed method transforms the known binary PCS/PZCS sets with odd length of sub-sequences into quaternary...

  • Binary Signal.  // Network Dictionary;2007, p66 

    A definition of the term "Binary Signal" is presented. It refers to a signal that may assume either of two polarities, neither of which is zero. A bipolar signal may have a two-state non-return-to-zero (NRZ) or a three-state return-to-zero (RZ) binary coding scheme and is usually symmetrical...

  • Deobfuscate Non-Returning Calls and Call-Stack Tampering in Instruction Traces. Jing Qiu; Xiaohong Su; Peijun Ma // Advanced Materials Research;7/24/2014, Vol. 989-994, p1782 

    Instruction traces are essential for dynamic analysis in reverse engineering. Code in instruction traces is often obfuscated to hinder analysts from understanding and analyzing in malware and binaries that protected by packers. Non-returning calls and call-stack tampering are two typical kinds...

  • Gray Codes Avoiding Matchings. Dimitrov, Darko; Dvor�k, Tom�; Regor, Petr; �krekovski, Riste // Discrete Mathematics & Theoretical Computer Science (DMTCS);2009, Vol. 11 Issue 2, p123 

    A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2n binary strings of length n such that consecutive strings differ in a single bit. Equivalently, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Qn, and a cyclic Gray code as a Hamiltonian cycle of...

  • Molecular interactions studies in liquid mixture using Ultrasonic technique. Priya, C. Shanmuga; Nithya, S.; Velraj, G.; Kanappan, A. N. // International Journal of Advanced Science & Technology;2010, Vol. 18, p59 

    Density, viscosity and ultrasonic velocity have been measured for binary liquid mixtures containing Methylmethacrylate+2-Methoxy ethanol, Methylmethacrylate +2-Ethoxy ethanol, Methyl methacrylate+2 Butoxy ethanol at 303K. The adiabatic compressibility, free length, free volume, internal...

  • NEW EXTREMAL BINARY SELF-DUAL CODES OF LENGTH 68 FROM R2-LIFTS OF BINARY SELF-DUAL CODES. KARADENIZ, SUAT; YILDIZ, BAHATTIN // Advances in Mathematics of Communications;May2013, Vol. 7 Issue 2, p219 

    A lift of binary self-dual codes to the ring R2 is described. By using this lift, a family of self-dual codes over R2of length 17 are constructed. Taking the binary images of these codes, extremal binary self-dual codes of length 68 are obtained. For the first time in the literature, extremal...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics