Prefix-reversal Gray Codes - Alexey Medvedev
Prefix-reversal Gray codesAlexey MedvedevCentral European University, Budapest, Hungary,Sobolev Institute of Mathematics, Novosibirsk, Russiajoint work withElena Konstantinova, Sobolev Institute of MathematicsDepartment of Mathematics and its ApplicationsCEU, 25.02.2015Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20151 / 31
Binary Reflected Gray codeHamming cube Hn [F. Gray, (1953), U.S. Patent 2,632,058]The first Gray code was introduced relative to binary stringsn 2:00 01 11 10000 001 011 010 110 111 101 100n 3:10110100001000111100101011001H3H2Alexey Medvedev (CEU, IM SBRAS)110Prefix-reversal Gray codes1110CEU–201511112 / 31
Gray codes are usefulThe Gray codes are used in many applications inmathematics;computer science;electrical engineering;data communications;etc.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20153 / 31
Example: HDDAlexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20154 / 31
Example: spinning wheelAlexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20155 / 31
Example: spinning wheel101111111110110?1010011001.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20156 / 31
Example: spinning wheelAlexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20157 / 31
Example: spinning wheel0011?111001Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20158 / 31
Gray codesCombinatorial Gray codes [J. Joichi et al., (1980)]A combinatorial Gray code is now referred as a method of generatingcombinatorial objects so that successive objects differ in somepre-specified, usually small, way.[D.E. Knuth, The Art of Computer Programming, Vol.4 (2010)]Knuth recently surveyed combinatorial generation:Gray codes are related toefficient algorithms for exhaustively generating combinatorial objects.(tuples, permutations, combinations, partitions, trees)Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–20159 / 31
Example: generating permutationsSteinhaus-Johnson-Trotter algorithm, (1964)List all the n! permutations, such that the successive permutations differby transposition of two adjacent 34]Generating permutations in Sym4Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201510 / 31
Example: generating permutationsSteinhaus-Johnson-Trotter algorithm, Figure: Hamilton cycle in Cay(Sym4 , {(1 2), (2 3), (3 4)}Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201511 / 31
Relation between codes and graphsDefine the graph Γ (V, E), where V – the set of combinatorial objectsand (u, v) E iff u and v differ in ”pre-specified small way”. Thenthe Hamilton path in Γ Gray code on V ;the Hamilton cycle in Γ cyclic Gray code on V .Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201512 / 31
AntiExample: generating permutationsSymmetric group Symn [R. Eggleton, W. Wallis, (1985); D. Rall,P. Slater, (1987)]The group of permutations:Q: Is it possible to list all permutations in a list so that each one differsfrom its predecessor in every position?A: nerating permutations in Sym4Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201513 / 31
Gray codes: generating permutations[S. Zaks, (1984)]Zaks’ algorithm:each successive permutation is generated by reversing a suffix of thepreceding permutation.Describe in terms of prefixes:Start with In [12 . . . n];Let ζn be the sequence of sizes of these prefixes defined by recursivelyas follows:ζ2 2ζn (ζn 1 n)n 1 ζn 1 , n 2,where a sequence is written as a concatenation of its elements;Flip prefixes according to the sequence.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201514 / 31
Zaks’ algorithm: examplesIf n 2 then ζ2 2 and we have:[12] [21]If n 3 then ζ3 23232 and we have:[123] [312] [231][213] [132] [321]If n 4 then ζ4 23232423232423232423232 and we have:[1234] [4123] [3412] [2341][2134] [1423] [4312] [3241][3124] [2413] [1342] [4231][1324] [4213] [3142] [2431][2314] [1243] [4132] [3421][3214] [2143] [1432] [4321]Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201515 / 31
Greedy Gray code: generating permutations[A. Williams, J. Sawada, (2013)]Describe in terms of prefixes:Start with In [12 . . . n];Take the largest size prefix we can flip not repeating a createdpermutation;Flip this prefix.Example: for n 4 then we have[1234] [4321] [2341] [1432] [3412] [2143] [4123] [3214][2314] [4132] [3142] [2413] [1423] [3241] [4231] [1324][3124] [4213] [1243] [3421] [2431] [1342] [4312] [2134]Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201516 / 31
Prefix–reversal Gray codes: generating permutationsEach ’flip’ is formally known as prefix–reversal.The Pancake graph Pnis the Cayley graph on the symmetric group Symn with generating set{ri Symn , 2 6 i 6 n}, where ri is the operation of reversing the orderof any substring [1, i], 1 i 6 n, of a permutation π when multiplied onthe right, i.e., [π1 . . . πi πi 1 . . . πn ]ri [πi . . . π1 πi 1 . . . πn ].Cycles in Pn [A. Kanevsky, C. Feng, (1995); J.J. Sheu, J.J.M. Tan,K.T. Chu, (2006)]All cycles of length , where 6 6 6 n!, can be embedded in the Pancakegraph Pn , n 3, but there are no cycles of length 3, 4 or 5.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201517 / 31
Pancake graphs: hierarchical structurePn consists of n copies of Pn 1 (i) (V i , E i ), 1 6 i 6 n, where the vertexset V i is presented by permutations with the fixed last [312]r3r2[132]Alexey Medvedev (CEU, IM 412]Prefix-reversal Gray 241]r2r4[4123]r2r4r3[2143]CEU–201518 / 31
Two scenarios of generating permutations: Zaks WilliamsBoth algorithms are based on independent cycles in Pn .Zaks’ prefix–reversal Gray code:Williams’ prefix–reversal Gray code:(r2 r3 )3 – flip the minimum number(rn rn 1 )n – flip the maximumof topmost pancakes that gives anumber of topmost pancakes thatnew stack.gives a new stack.r4 r2 r3r2 r3r2 r4 r2 r3 r3 r4r4 r4r4 r3 r4r4 r2 r3 r3r3(a) Zaks’ code in P4r2r4r2 r2 r2 Alexey Medvedev (CEU, IM SBRAS)r4r4r2 r3r3 r4 r3 r4r2r4r2 r3 r3 r3 r2r3r4r3r4 r2 r2 r3 (b) Williams’ code in P4Prefix-reversal Gray codesCEU–201519 / 31
Independent cycles in PnTheorem 1. (K., M.)The Pancake graph Pn , n 4, contains the maximal set of –cycles of the canonical formn! independentC (rn rm )k ,where 2 k, 2 6 m 6 n 1 and O(1) if m 6 b n2 c;O(n) if m b n2 c and n 0k O(n2 ) else.(1)(mod n m);(2)CorollaryThe cycles presented in Theorem 1 have no chords.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201520 / 31
Hamilton cycles based on small independent even cyclesHamilton cycle or path in Pn PRGCDefinitionThe Hamilton cycle Hn based on independent –cycles is called aHamilton cycle in Pn , consisting of paths of lengths l 1 ofindependent cycles, connected together with external to these cycles edges.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201521 / 31
Hamilton cycles based on small independent even cyclesDefinitionThe fastening cycle Hn0 to the Hamilton cycle Hn based on independentcycles is defined on unused edges of Hn and the same external edges.H4 H4 (c) Hamilton cycle H4 in P4Alexey Medvedev (CEU, IM SBRAS) (d) Fastening cycle H40 in P4Prefix-reversal Gray codesCEU–201522 / 31
Hamilton cycles based on the independent cycles in P4TheoremIn the Pancake graph P4 there are only four Hamilton cycles based on themaximal set independent cycles.Proof. The collection of all possible maximal sets of independent cycles ofthe same form in P4 is presented below by the following table:6–cycles8–cycles3C6 (r3 r2 )Alexey Medvedev (CEU, IM SBRAS)C81C8212–cycles4 (r4 r2 ) (r4 r3 )4Prefix-reversal Gray codes1C12 (r2 r3 r4 r3 r2 r4 )22C12 (r3 r2 r4 r2 r3 r4 )2CEU–201523 / 31
Hamilton cycles based on the independent cycles in P4TheoremIn the Pancake graph P4 there are only four Hamilton cycles based on themaximal set independent cycles.Proof. All possible cases of Hamilton cycles based on the independentcycles in P4 are presented in the table below:H4iH41H42H43H4424 ((r2 r3 ) r2 r4 ) ((r3 r2 )2 r3 r4 )4 ((r4 r3 )3 r4 r2 )3 ((r4 r2 )3 r4 r3 )3Alexey Medvedev (CEU, IM SBRAS)H4iH41H42H43H44 (r4 r3 )4 (r4 r2 )4 (r3 r2 )3 (r2 r3 )3Prefix-reversal Gray codesDescriptionZaks’ Hamiltonian cycle;based on independent cycles C6 ;Williams’ Hamiltonian cycle;based on independent cycles C8 .CEU–201524 / 31
Hamilton cycles based on the independent cycles in P4TheoremIn the Pancake graph P4 there are only four Hamilton cycles based on themaximal set independent cr2bcbcbcr2bcr4bcr2bcr4bcr2bcr4r3(e) Hamiltonian cycle (H42 , H42 ) in P4Alexey Medvedev (CEU, IM r2bcr4bcr3bcbcr3bcr3r3bcr2bcbcr2bcr4(f) Hamiltonian cycle (H44 , H44 ) in P4Prefix-reversal Gray codesCEU–201525 / 31
Non-existence of Hamilton cyclesSuppose the fastening cycle Hn0 has form (rm rj )t , where m {2, . . . , n},rj PR\{rm }.Theorem 2. (K., M.)The only Hamilton cycles Hn based on independent cycles from Theorem 1with the fastening cycle Hn0 of form (rm rj )t , where m {2, . . . , n}, areZaks’, Greedy and Hamilton cycle based on (r4 r2 )4 in P4 .Proof. Hn0 (rm rj )t Hn0 has form from Theorem 1. Thus, thefollowing inequality should hold2n!Lmax6 Lmax ,(3)where Lmax is the maximal length of cycles from Theorem 1.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201526 / 31
Non-existence of Hamilton cyclesThe length Lmax can be estimated asLmax 6 n(n 2),and therefore2n! 6 L2max ,1n! 6 n2 (n 2)2 .2The inequality does not hold starting from n 7. For n from 4 to 6 it iseasy to verify using the exact lengths that inequality holds only for n 4.2Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201527 / 31
Non-existence of Hamilton cyclesSuppose the fastening cycle Hn0 has form Hn0 (rm rξ )t , where by rξ wemean that every second reversal may be different from previous.Another way of thinking of it is to treat rξ as a random variable takingvalues in P R\{rn , rm } with some distribution.Theorem 3. (K., M.)The only Hamilton cycles Hn based on independent cycles fromTheorem 1 with the fastening cycle Hn0 of form (rm rξ )t , wherem 6 {n, n 2} and rξ PR\{rn , rm } is Greedy Hamilton cycle in Pn .Proof is based on structural properties of the graph, hierarchical structureand length’s argument above.Remark. Existence in the case m n 2 is only unresolved when O(n).Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201528 / 31
Hamilton cycles based on small independent even cyclesOpen problemSuppose the fastening cycle Hn0 has form Hn0 (rη rξ )t , whererη {rn , rm } and rξ P R\{rn , rm }.Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201529 / 31
PRGC: hierarchical constructionHierarchical constructionSuppose we know a bunch of Hamilton cycle constructions in graph Pn 1 .Then the PRGC can be constructed using the fastening 2n–path passingthrough all copies of Pn 1 in Pn exactly once.Example:Pn 1 (n)π2Zaks’ construction:rnPn 1(n 1)Lnn 1π1rnπ3π2nLn 1n 1L1n 1Hn01 (rn rn 1 )nπ4rnrnπ5Ln 2n 1Pn 1(1)rnPn 1(n 2)Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201530 / 31
Thank you for your attention!Alexey Medvedev (CEU, IM SBRAS)Prefix-reversal Gray codesCEU–201531 / 31
[1342] [3241] [2143] [1324] [3214] [2134] Generating permutations in Sym4 Alexey Medvedev (CEU, IM SBRAS) Pre x-reversal Gray codes CEU{2015 10 / 31. Example: generating permutations . 2Ei uand vdi er in "pre-speci ed small way". Then the Hamilton path in Gray code on V; the Hamilton
During 1969 the Hi-Power pistol Serial Number code was changed to a two digit year and "C" prefix. Serial Numbers for "T" prefix Hi-Power pistols exceeded T300000 and were shipped into 1970. Year ser. # PreFiX COde 1969 69C prefix before Ser. No. 1970 70C prefix before Ser. No. 1971 196471C prefix before Ser. No. 1972 72C prefix before Ser. No.
To Add a Prefix or Suffix: 1. Scan command barcode of " Add Prefix" or" Add Suffix ". 2. Check the prefix or suffix hex value from the ASCII Chart. 3. Scan the 2 digit hex value from the Numeric Bar Codes 4. Repeat Steps 2 and 3 for all the prefix or suffix that you want to add. 5. Scan the output format to enable or disable prefix/suffix output.
Parallel Prefix Adder[13,15,2] The parallel prefix adder is a kind of carry look-ahead adders that accelerates a n-bit addition by means of a parallel prefix carry tree. A block diagram of a prefix adder Input bit propagate, generate, and not kill cells Output sum cells The prefix carry tree G z "group generate"x signal across the bits from x .
Prefix Origins: ‘audi ’ online test Prefix Origins: ‘trans’ online test Prefix Origins: ‘volve’ online test Look, Cover Write online activity Printable activity sheet Prefix Origins: ‘audi’ online instructional video Printable activity sheet Prefix Origins: ‘trans’ online instructional video Look, Cover Write online activity
complete prefix codes. iven by the followi example. Let T be local language over (a, 6, c) defined by the set of forbidden factors T-complete (non-prefix) de is X (a, b, bc). ne can verify that no finite T- complete prefix code exis evious example also shows that ich are maximal as prefix T-codes.
employee is not paying back with a payroll check or direct deposit reversal. 24 Questions. Email Us: PayrollReversalAndExchange@osc.ny.gov. 25 Completing a Partial Check Reversal. Jared Waldron, Laurie Leahey, and Kevin Czmyr. 26 Partial Check Reversal Review two example reversals.
Standard Colors Leatherette* Cloth/cloth* Black P4 PL Gray PU PT Blue FE FC Burgundy AA A9 Tan 61 6R Brown N/A 6Q Black with red insert P5 PM Black with gray insert P6 PN Black with tan insert P7 PP Black with blue insert P8 PQ Gray with black insert PX n/a Gray with blue insert PV n/a Gray with red insert PW n/a Blue with gray insert FF FD
The report of last year’s Commission on Leadership – subtitled No More Heroes (The King’s Fund 2011) – called on the NHS to recognise that the old ‘heroic’ leadership by individuals – typified by the ‘turnaround chief executive’ – needed to make way for a model where leadership was shared both ‘from the board to the ward’ and across the care system. It stressed that one .
