An Efficient Algorithm for Permutation Iteration Using a Singly Linked List

2025/01/17 by Thomas Baruchel, Baruchel, Thomas
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Computer science #Mathematics #Permutation (music) #Physics #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2501.10102

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We present a new content-agnostic 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.

Related

• A Versatile Algorithm to Generate Various Combinatorial Structures
• Multi-level Loop-less Algorithm for Multi-set Permutations
• Permutation Generation: Two New Permutation Algorithms
• Strictly In-Place Algorithms for Permuting and Inverting Permutations
• A Recursive Algorithmic Approach to the Finding of Permutations for the Combination of Any Two Sets