Abstract
The set of permutations of 〈n〉={1,…,n} in one-line notation is Π(n). The shorthand encoding of a 1⋯a n ∈Π(n) is a 1⋯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–996, 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)–(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’.
Similar content being viewed by others
References
Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discrete Math. 110, 43–59 (1992)
Compton, R.C., Williamson, S.G.: Doubly adjacent Gray codes for the symmetric group. Linear Multilinear Algebra 35(3), 237–293 (1993)
Corbett, P.F.: Rotator graphs: an efficient topology for point-to-point multiprocessor networks. IEEE Trans. Parallel Distrib. Syst. 3, 622–626 (1992)
Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Holroyd, A., Ruskey, F., Williams, A.: Faster generation of shorthand universal cycles for permutations. In: Proceedings of the 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam, July 19–21. LNCS, vol. 6196, pp. 298–307. Springer, Berlin (2010)
Jackson, B.: Universal cycles of k-subsets and k-permutations. Discrete Math. 149, 123–129 (1996)
Johnson, J.R.: Universal cycles for permutations. Discrete Math. 309, 5264–5270 (2009)
Johnson, S.M.: Generation of permutations by adjacent transpositions. Math. Comput. 17, 282–285 (1963)
Knuth, D.E.: The Art of Computer Programming, vol. 4, Generating All Tuples and Permutations, Fascicle 2. Addison-Wesley, Reading (2005)
Knuth, D.E.: The Art of Computer Programming, vols. 1–4A Boxed Set, 3rd edn. Addison-Wesley Professional, Reading (2011)
MacGregor, J.N., Ormerod, T.: Human performance on the traveling salesman problem. Percept. Psychophys. 58(4), 527–539 (1996)
Page, J., Salvia, J., Collewetb, C., Foresta, J.: Optimised De Bruijn patterns for one-shot shape acquisition. Image Vis. Comput. 23, 707–720 (2005)
Ruskey, F., Williams, A.: An explicit universal cycle for the (n−1)-permutations of an n-set. ACM Trans. Algorithms 6(3), article 45 (2010)
Scheinerman, E.R.: Determining planar location via complement-free de Bru** sequences using discrete optical sensors. IEEE Trans. Robot. Autom. 17(6), 883–889 (2001)
Sedgewick, R.: Permutation generation methods. Comput. Surv. 9, 137–164 (1977)
Sohn, H.S., Bricker, D.L., Simon, J.R., Hsieh, Y.C.: Optimal sequences of trials for balancing practice and repetition effects. Behav. Res. Methods Instrum. Comput. 29, 574–581 (1997)
Williams, A.: Loopless generation of multiset permutations using a constant number of variables by prefix shifts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4–6, pp. 987–996 (2009)
Williams, A.: Shift gray codes, PhD Thesis, University of Victoria (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by NSERC.
Rights and permissions
About this article
Cite this article
Holroyd, A.E., Ruskey, F. & Williams, A. Shorthand Universal Cycles for Permutations. Algorithmica 64, 215–245 (2012). https://doi.org/10.1007/s00453-011-9544-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9544-z