Abstract
Conventional wisdom suggests that O(k)-time is required to reverse a substring of length k. To reduce this time complexity, a simple and unorthodox data structure is introduced. A boustrophedon linked list is a doubly-linked list, except that each node does not differentiate between its backward and forward pointers. This lack of information allows substrings of any length to be reversed in O(1)-time. This advantage is used to efficiently unsort permutations using prefix-reversals. More specifically, this paper presents two algorithms that visit each successive permutations of 〈n 〉 = {1,2,...,n} in worst-case O(1)-time (i.e. loopless). The first visits the permutations using a prefix-reversal Gray code due to Zaks [22], while the second visits the permutations in co-lexicographic order. As an added challenge, both algorithms are non-probing since they rearrange the data structure without querying its values. To accomplish this feat, the algorithms are based on two integer sequences: A055881 in the OEIS [17] and an unnamed sequence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. SIAM J. Comput. 25(2), 272–289 (1996)
Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I.H., Voit, W.: An (18/11)n upper bound for sorting by prefix reversals. Theoretical Computer Science 410, 3372–3390 (2009)
Choset, H.: Coverage of known spaces: The boustrophedon cellular decomposition. Journal Autonomous Robots 9(3), 247–253 (2000)
Cohen, D.S., Blum, M.: On the problem of sorting burnt pancakes. Discrete Applied Mathematics 61, 105–120 (1995)
Ehrlich, G.: Loopless algorithms for generating permutations, combinations and other combinatorial configurations. Journal of the ACM 20(3), 500–513 (1973)
Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press, Cambridge (2009)
Gates, W.H., Papadimitriou, C.H.: Bounds for sorting by prefix reversal. Discrete Mathematics 27, 47–57 (1979)
Goldstein, A.J., Graham, R.L.: Sequential generation by transposition of all the arrangements of n symbols. In: Bell Telephone Laboratories (Internal Memorandum), Murray Hill, NJ (1964)
Kaplan, H., Shamir, R., Tarjan, R.E.: Faster and simpler algorithm for sorting signed permutations by reversals. In: SODA 1997: Proceedings of the eighth annual ACM-SIAM symposium on discrete algorithms, New Orleans, Louisiana, United States, pp. 178–187 (1997)
Knuth, D.E.: The Art of Computer Programming. volume 4 fasicle 2: Generating All Tuples and Permutations. Addison-Wesley, Reading (2005)
Knuth, D.E.: The Art of Computer Programming, volume 4 fasicle 3: Generating All Combinations and Partitions. Addison-Wesley, Reading (2005)
Knuth, D.E.: The Art of Computer Programming, volume 4 fasicle 4: Generating All Trees, History of Combinatorial Generation. Addison-Wesley, Reading (2006)
Korsh, J.F., Lipschutz, S.: Generating multiset permutations in constant time. Journal of Algorithms 25, 321–335 (1997)
Lehmer, D.H.: Teaching combinatorial tricks to a computer. In: Combinatorial Analysis. Proc. of Symposium Appl. Math., vol. 10, pp. 179–193. American Mathematical Society, Providence (1960)
Mares, M., Straka, M.: Linear-time ranking of permutations. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 187–193. Springer, Heidelberg (2007)
Millar, J., Sloane, N.J.A., Young, N.E.: A new operation on sequences: the boustrouphedon transform. Journal of Comb. Theory, Series A 76(1), 44–54 (1996)
Sloane, N.: (2010), http://www.research.att.com/~njas/sequences/A055881
Steinhaus, H.: One Hundred Problems in Elementary Mathematics. Pergamon Press, Oxford (1963); Reprinted by Dover Publications in 1979 (1979)
Wikipedia (2009), http://en.wikipedia.org/wiki/Boustrophedon
Williams, A.: Loopless generation of multiset permutations using a constant number of variables by prefix shifts. In: SODA 2009: The Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, USA (2009)
YouTube. 2009 National Sweet Corn Eating Championship (2009), http://www.youtube.com/watch?v=EUy56pBA-HY
Zaks, S.: A new algorithm for generation of permutations. BIT Numerical Mathematics 24(2), 196–204 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Williams, A. (2010). O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List. In: Boldi, P., Gargano, L. (eds) Fun with Algorithms. FUN 2010. Lecture Notes in Computer Science, vol 6099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13122-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-13122-6_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13121-9
Online ISBN: 978-3-642-13122-6
eBook Packages: Computer ScienceComputer Science (R0)