mapFolding
Exact enumeration tools for map folding, stamp folding, semi-meanders, and meanders.
mapFolding is a typed Python research package for counting distinct foldings of one- and multidimensional maps. It provides:
- stable dispatch functions for ordinary, rotationally symmetric, and divided computations;
- native algorithms for map folding, semi-meanders, and meanders;
- a unified interface to 33 implemented OEIS sequences, including exact formula relationships;
- readable source algorithms, generated optimized implementations, and optional NumPy, Numba, Pandas, and Codon routes; and
- cross-implementation tests against known sequence values.
Earlier versions of this project were used to compute new terms for OEIS A001415, the number of ways to fold a 2 × n strip of stamps.
This is exact combinatorial enumeration: running time and memory requirements grow quickly. Start with small inputs. The supported high-level interfaces are in mapFolding.basecamp and mapFolding.oeis; other modules include evolving research code.
Installation
mapFolding requires Python 3.13 or newer.
pip install mapFolding
Install an optional backend only when you need its corresponding implementation:
| Extra | Purpose |
|---|---|
numba |
Numba-compiled map-folding implementations |
pandas |
Pandas and Arrow meander implementation |
codon |
Codon-compiled implementations on Linux |
ortools |
Experimental constraint-propagation work |
testing |
Test dependencies |
development |
Broader development and analysis dependencies |
For example:
pip install "mapFolding[numba,pandas]"
Quick start
Count map foldings
Each positive integer in mapShape is the length of one dimension. A (2, 3) map has six leaves.
from mapFolding.basecamp import countFolds
totalFolds = countFolds((2, 3))
print(totalFolds) # 60
Calculate an OEIS term
from mapFolding.oeis import oeisIDfor_n
totalFolds = oeisIDfor_n('A001415', 6)
print(totalFolds) # 10512
The installed commands expose the same sequence registry:
getOEISids
OEIS_for_n A001415 6
The second command prints:
10512 distinct folding patterns.
Time elapsed: ... seconds
Count semi-meanders and meanders
from mapFolding.basecamp import countMeanders
print(countMeanders('semi', 5)) # 10; OEIS A000682
print(countMeanders('meanders', 4)) # 3; OEIS A005316
Public interfaces
| Goal | Interface |
|---|---|
| Count all foldings of a map | mapFolding.basecamp.countFolds(mapShape, ...) |
| Count rotationally symmetric foldings | mapFolding.basecamp.countFoldsSymmetric(mapShape, ...) |
| Count semi-meanders or meanders | mapFolding.basecamp.countMeanders(kind, n, ...) |
| Calculate any implemented OEIS term | mapFolding.oeis.oeisIDfor_n(oeisID, n, ...) |
| Convert a map-folding OEIS index to dimensions | mapFolding.oeis.makeMapShape(oeisID, n) |
| Retrieve cached known values | mapFolding.oeis.getValuesKnown(oeisID) |
| List implemented sequences | getOEISids |
oeisIDfor_n dispatches to the appropriate folding algorithm, meander algorithm, symmetric-folding algorithm, or exact formula. Run getOEISids for the current list and descriptions of all supported sequences.
The map-folding sequence mappings are:
| OEIS ID | Problem | mapShape for index n |
|---|---|---|
| A000136 | Strip of n labeled stamps |
(1, n) |
| A001415 | 2 × n strip |
(2, n) |
| A001416 | 3 × n strip |
(3, n) |
| A001417 | n-dimensional 2 × ⋯ × 2 map |
(2,) * n |
| A195646 | n-dimensional 3 × ⋯ × 3 map |
(3,) * n |
| A001418 | n × n sheet |
(n, n) |
| A007822 | Symmetric foldings of 2n + 1 stamps |
(1, 2 * n) |
For A007822, pass (1, 2 * n) to countFoldsSymmetric; the function's computational shape differs from the 2n + 1 stamps in the sequence description.
OEIS metadata and b-files are cached locally for 30 days. Missing or stale entries are refreshed from oeis.org; stale cached data remains available if a refresh fails.
Algorithm selection and long computations
Leave flow='' for the default implementation. The alternate selectors exist for research, validation, and performance comparisons:
| Interface | Supported flow values |
|---|---|
countFolds |
'', daoOfMapFolding, numba, theorem2, theorem2Codon, theorem2Numba, theorem2Trimmed |
countFoldsSymmetric |
'', asynchronous, theorem2, theorem2Codon, theorem2Numba, theorem2Trimmed |
countMeanders |
'', matrixMeanders, matrixNumPy, matrixPandas |
The Numba, Pandas, and Codon selectors require their corresponding extras. For OEIS sequences with multiple exact identities, the f argument to oeisIDfor_n selects a formula; leaving it empty uses the default route.
Pass pathLikeWrite to a counting function to preserve a result. An existing directory receives a generated filename such as p2x6.totalFolds; an explicit target file is also supported. The destination is write-tested before computation, and an existing target is not overwritten.
countFolds can split work with an integer, computationDivisions='cpu', or computationDivisions='maximum'. Dividing this algorithm repeats substantial work and is usually slower, so leave computationDivisions=None unless you are deliberately studying the parallel implementation.
Repository guide
| Path | Role |
|---|---|
mapFolding/basecamp.py |
Stable high-level dispatch for folding and meander computations |
mapFolding/oeis/ |
OEIS dispatch, formulas, metadata, and cached values |
mapFolding/algorithms/ |
Handwritten source algorithms |
mapFolding/synthesized/ |
Generated implementations; regenerate these instead of editing them directly |
mapFolding/kitAST/ |
Project-specific AST transformations and module generators |
mapFolding/_e/ |
Experimental elimination-based algorithms and analysis |
mapFolding/tests/ |
Main correctness, dispatch, filesystem, and parameter tests |
mapFolding/reference/ |
Historical implementations, completed jobs, notes, and research artifacts |
easyRun/ |
Benchmark and exploration harnesses |
General-purpose transformation primitives developed alongside this project now live in astToolkit and astToolFactory. The transformation pipeline retained here is specific to generating and validating mapFolding implementations.
Development
Create and activate a virtual environment, then install both development extras:
git clone https://github.com/hunterhogan/mapFolding.git
cd mapFolding
python -m venv .venv
PowerShell:
.venv\Scripts\Activate.ps1
POSIX shells:
source .venv/bin/activate
Install and test:
pip install -e ".[development,testing]"
pytest
The test suite compares independent implementations with known OEIS values and stored data samples. When adding an algorithm variant, begin with mapFolding/tests/test_computations.py and register the new flow beside the existing implementations.
Citation
To cite this software, use the metadata in CITATION.cff. BibTeX files for the mathematical literature are collected in citations/.
Research references
Sur les Chevauchements des Permutations
- BibTeX citation.
- PDF: OEIS
Folding a strip of stamps
A map-folding problem
Multi-dimensional map-folding
- BibTeX citation.
- DOI: 10.1093/comjnl/14.1.75
- PDF: Oxford Academic
- Java implementation by Sean A. Irvine.
A transfer matrix approach to the enumeration of plane meanders
- BibTeX citation. TeX Source with precise formulas for AI agents.
- DOI: 10.1088/0305-4470/33/34/301
- Free preprint: arXiv:cond-mat/0008178
- C# implementation described by Andrew Howroyd. BibTeX citation.
Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms
Foldings and meanders
- BibTeX citation. TeX Source with precise formulas for AI agents.
- PDF: The Australasian Journal of Combinatorics
- Free preprint: arXiv:1302.2025
jOEIS: Java Online Encyclopedia of Integer Sequences
The Online Encyclopedia of Integer Sequences
Computing new values
- Folds of multidimensional map (2, 2, 2, 2, 2, 2, 2, 2), which is A001417(8): estimated 14 days with my current hardware and a non-published algorithm.
- Folds of multidimensional map (2, 21), which is A001415(21): estimated 6 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Folds of multidimensional map (2, 22), which is A001415(22): estimated 15 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Folds of multidimensional map (3, 15), which is A001416(15): estimated 11 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Semi-meanders with 46 crossings, which is A000682(46): estimated 1–2 hours if I had 64 GB of system memory.
Computation times assume:
- No power interruptions. (I don't have a UPS, and in the last two months the longest gap between power interruptions was 8 days 6 hours.)
- No system crashes.
- Single-core computations are given priority over other tasks.
- The core of single-core computations is regularly boosted.
- No heat issues.
My recovery
1 maintainer
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Filter files by name, interpreter, ABI, and platform.
If you're not sure about the file name format, learn more about wheel file names.
Copy a direct link to the current filters
File details
Details for the file mapfolding-0.33.0.tar.gz.
File metadata
- Download URL: mapfolding-0.33.0.tar.gz
- Upload date:
- Size: 325.4 kB
- Tags: Source
- Uploaded using Trusted Publishing? Yes
- Uploaded via:
twine/7.0.0 CPython/3.13.14
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
e0409512cc208824744daff31482c35c4f4f51aee7eed20db45e7c3760de4f9e
|
|
| MD5 |
8e296740d78e256e4468d91487a2348c
|
|
| BLAKE2b-256 |
8b370e0dce14aa1ed7c2fce02f9d90c6089561dfa0e6730c05c8e01983f976fa
|
File details
Details for the file mapfolding-0.33.0-py3-none-any.whl.
File metadata
- Download URL: mapfolding-0.33.0-py3-none-any.whl
- Upload date:
- Size: 409.4 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? Yes
- Uploaded via:
twine/7.0.0 CPython/3.13.14
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
159c943aff951d7fefb0b2a49787a63e317807c506871c9ee7b8247b8e31c87f
|
|
| MD5 |
2f9b6218bd32a64d69d81f6b8233857e
|
|
| BLAKE2b-256 |
ef9f2a2bb756295e0419b6e1a36338bc76ea7a3352a2802541757cfc70f5f416
|
