An Efficient Algorithm for Permutation Iteration Using a Singly Linked List
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914037305966592 |
|---|---|
| author | Baruchel, Thomas |
| author_facet | Baruchel, Thomas |
| contents | We present a new algorithm for iterating over all permutations of a sequence. The algorithm leverages elementary~$O(1)$ operations on recursive lists. As a result, no new nodes are allocated during the computation. Instead, all elements are rearranged within the original nodes of the singly linked list throughout the process. While permutations are generated in an unusual order, the transitions between consecutive permutations remain smooth. A proof of concept written in the Lisp programming language is referenced and discussed. We also present a polynomial-time algorithm for computing an arbitrary permutation given its index. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10102 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Efficient Algorithm for Permutation Iteration Using a Singly Linked List Baruchel, Thomas Data Structures and Algorithms Discrete Mathematics Combinatorics 05A05 G.2.1; E.1 We present a new algorithm for iterating over all permutations of a sequence. The algorithm leverages elementary~$O(1)$ operations on recursive lists. As a result, no new nodes are allocated during the computation. Instead, all elements are rearranged within the original nodes of the singly linked list throughout the process. While permutations are generated in an unusual order, the transitions between consecutive permutations remain smooth. A proof of concept written in the Lisp programming language is referenced and discussed. We also present a polynomial-time algorithm for computing an arbitrary permutation given its index. |
| title | An Efficient Algorithm for Permutation Iteration Using a Singly Linked List |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 05A05 G.2.1; E.1 |
| url | https://arxiv.org/abs/2501.10102 |