A short note on computing permutations

• Autorzy: Gburzyński Paweł , Zalewski Janusz

Identyfikatory

DOI

10.15439/2023F5568

• Języki publikacji: EN

Abstrakty

EN

We discuss an algorithm for generating all permutations of numbers between 1 and N. The algorithm is short and efficient, yet its behavior is not obvious from the code, mostly owing to the recursion. The discussion touches upon a few interesting methodological issues and brings in an educational case study in recursion.

Słowa kluczowe

EN

algorithm; recursion; permutation; algorithm analysis

PL

algorytm; rekurencja; permutacja; analiza algorytmów

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 979--982
• Opis fizyczny: Bibliogr. 13 poz., il.

Twórcy

autor

Gburzyński Paweł

• Department of Computer Engineering Vistula University ul. Stokłosy 3, 02-787 Warsaw, Poland

• https://orcid.org/0000-0002-1844-6110

autor

Zalewski Janusz

• Department of Informatics Ignacy Mościcki State Professional College ul. Narutowicza 9, 06-400 Ciechanów, Poland

• https://orcid.org/0000-0002-2823-0153

Bibliografia

• 1. D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming). Addison-Wesley Professional, 2005.
• 2. L. Banachowski, A. Kreczmar, and W. Rytter, Analysis of Algorithms and Data Structures. Addison-Wesley Longman Publishing Co., Inc., 1991.
• 3. P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge University Press, 2009.
• 4. A. Oram and G. Wilson, Beautiful code: Leading programmers explain how they think. O’Reilly Media, Inc, 2007.
• 5. G. Ehrlich, “Loopless algorithms for generating permutations, combinations, and other combinatorial configurations,” Journal of the ACM, vol. 20, no. 3, pp. 500–513, 1973.
• 6. G. Mirkowska and A. Salwicki, Algorithmic Logic. PWN, Warszawa, 1987. [Online]. Available: http://lem12.uksw.edu.pl/wiki/Algorithmic Logic
• 7. N. Dershowitz, “A simplified loop-free algorithm for generating permutations,” BIT Numerical Mathematics, vol. 15, no. 2, pp. 158–164, 1975.
• 8. C. W. Ko and F. Ruskey, “Generating permulations of a bag by interchanges,” Information Processing Letters, vol. 41, no. 5, pp. 263–269, 1992.
• 9. D. R. van Baronaigien and F. Ruskey, “Generating permutations with given ups and downs,” Discrete Applied Mathematics, vol. 36, no. 1, pp. 57–65, 1992.
• 10. S. Effler and F. Ruskey, “A CAT algorithm for generating permutations with a fixed number of inversions,” Information Processing Letters, vol. 86, no. 2, pp. 107–112, 2003.
• 11. O.-J. Dahl and K. Nygaard, “Simula,” in Encyclopedia of Computer Science. Wiley, 2003, pp. 1576–1578.
• 12. D. Beazley and B. K. Jones, Python cookbook: Recipes for mastering Python 3. “O’Reilly Media, Inc.”, 2013.
• 13. D. E. Knuth, “Literate programming,” The Computer Journal, vol. 27, no. 2, pp. 97–111, 1984.

Uwagi

1. Thematic Tracks Short Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).