Public
- Public
- Network
- Groups
- Featured
- Popular
- People

Conversation

Notices

Embed this notice
José A. Alonso (jose_a_alonso@mathstodon.xyz)'s status on Tuesday, 21-Jan-2025 03:37:27 JST José A. Alonso

An efficient algorithm for permutation iteration using a singly linked list. ~ Thomas Baruchel. https://arxiv.org/abs/2501.10102v1 #CommonLisp #Algorithms
In conversation about a month ago from mathstodon.xyz permalink
Attachments
1. Domain not in remote thumbnail source whitelist: arxiv.org
  
  An Efficient Algorithm for Permutation Iteration Using a Singly Linked List
  
  We present a new algorithm for iterating over all permutations of a sequence. The algorithm leverages elementary operations on recursive lists. Within each recursive call, only two operations are required to generate all permutations (albeit in an unusual order): swapping the first two elements of the list or moving the last element to the front. 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. A proof of concept written in the Lisp programming language is proposed and discussed.
- screwlisp and Arne Babenhauserheide repeated this.
- Embed this notice
  th. baruchel (baruchel@functional.cafe)'s status on Tuesday, 21-Jan-2025 03:37:42 JST th. baruchel
  in reply to
  
  @Jose_A_Alonso Thank you for referencing that paper! If you'd like a quick look at the #Lisp code, feel free to check out the snippet I uploaded here:
  https://git.univ-pau.fr/tbaruchel/numerical-routines/-/snippets/5
  The core concept of the algorithm is to iterate in-place over all permutations, efficiently reusing all nodes of the native Lisp list.
  
  In conversation about a month ago permalink

Public

Conversation

Notices

Feeds