Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.00111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911293936500736 |
|---|---|
| author | Chen, Dexin |
| author_facet | Chen, Dexin |
| contents | The rotation of multi-dimensional arrays, or tensors, is a fundamental operation in computer science with applications ranging from data processing to scientific computing. While various methods exist, achieving this rotation in-place (i.e., with O(1) auxiliary space) presents a significant algorithmic challenge. The elegant three-reversal algorithm provides a well-known O(1) space solution for one-dimensional arrays. This paper introduces a generalization of this method to N dimensions, resulting in the "$2^n+1$ reversal algorithm". This algorithm achieves in-place tensor rotation with O(1) auxiliary space and a time complexity linear in the number of elements. We provide a formal definition for N-dimensional tensor reversal, present the algorithm with detailed pseudocode, and offer a rigorous proof of its correctness, demonstrating that the pattern observed in one dimension ($2^1+1=3$ reversals) and two dimensions ($2^2+1=5$ reversals) holds for any arbitrary number of dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_00111 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An O(1) Space Algorithm for N-Dimensional Tensor Rotation: A Generalization of the Reversal Method Chen, Dexin Data Structures and Algorithms The rotation of multi-dimensional arrays, or tensors, is a fundamental operation in computer science with applications ranging from data processing to scientific computing. While various methods exist, achieving this rotation in-place (i.e., with O(1) auxiliary space) presents a significant algorithmic challenge. The elegant three-reversal algorithm provides a well-known O(1) space solution for one-dimensional arrays. This paper introduces a generalization of this method to N dimensions, resulting in the "$2^n+1$ reversal algorithm". This algorithm achieves in-place tensor rotation with O(1) auxiliary space and a time complexity linear in the number of elements. We provide a formal definition for N-dimensional tensor reversal, present the algorithm with detailed pseudocode, and offer a rigorous proof of its correctness, demonstrating that the pattern observed in one dimension ($2^1+1=3$ reversals) and two dimensions ($2^2+1=5$ reversals) holds for any arbitrary number of dimensions. |
| title | An O(1) Space Algorithm for N-Dimensional Tensor Rotation: A Generalization of the Reversal Method |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.00111 |