a stupid implementation for the stamp folding problem. It's quite inefficient but works!

stamp_folding_naive.py

from enum import Enum
import copy

class FoldDirection(Enum):
    Right = "r"
    Left = "l"

class FoldingPaper:

    def __init__(self, num_segments, perm_arr=None):
        self.num_segments = num_segments

        # the paper is represented as a dictionary where
        # every key represents a position that different papers are stacked on.
        # For example, if num_segments=2:
        #     perm_arr = {0: [0], 1: [1]}
        # then if we fold left along the only edge we want:
        #     perm_arr = {0: [1, 0]}
        # which represents the fully folded state where
        # segment #1 has been folded ontop of segment #0

        self.perm_arr = {
            n: [n] for n in range(num_segments)
        } if perm_arr is None else perm_arr
        
    def __len__(self):
        """length of the paper gives the number of (combined) segments. Hence, length - 1 is number of available folds"""
        return len(self.perm_arr)

    def copy(self):
        """create a deep copy of the segmented paper"""
        perm_arr_copy = copy.deepcopy(self.perm_arr)
        return self.__class__(self.num_segments, perm_arr_copy)

    def to_tuple(self):
        """if all segments lie on top of each other, get the resulting permutation"""
        assert len(self) == 1
        return tuple(self.perm_arr[0])
    
    def _put_perm_on_perm(self, from_index, put_index):
        """helper method to put one stack at `from_index` on `put_index` (but reversed, as we fold it)"""
        if put_index not in self.perm_arr:
            self.perm_arr[put_index] = []
        self.perm_arr[put_index] += reversed(self.perm_arr[from_index])
        del self.perm_arr[from_index]

    def _sort_perm_arr(self):
        """correct the minimum index such that perm_arr is 0 indexed"""
        new_perm_arr = {}
        min_key = min(self.perm_arr.keys())
        max_key = max(self.perm_arr.keys())
        for new_i, old_i in enumerate(range(min_key, max_key + 1)):
            new_perm_arr[new_i] = self.perm_arr[old_i]
        self.perm_arr = new_perm_arr

    def fold_along(self, crease_index, direction: FoldDirection):
        """perform a fold along a given `crease_index` with `direction`
        
        the crease_indexes are 0 indexed between the segments. To fold segment 0
        on segment 1, perform a Right-Fold along crease 0.
        """
        assert 0 <= crease_index < len(self.perm_arr) - 1

        if direction == FoldDirection.Left:
            for i in range(crease_index + 1):
                delta = abs(crease_index - i)
                target_i = i + delta * 2 + 1
                self._put_perm_on_perm(i, target_i)
        
        if direction == FoldDirection.Right:
            for i in range(crease_index + 1, len(self.perm_arr)):
                delta = abs(crease_index - i)
                target_i = i - delta * 2 + 1
                self._put_perm_on_perm(i, target_i)

        self._sort_perm_arr()

# prepare set of all reached permutations (that avoids duplicates!)
# (we have to use a set, as many permutations are reachable by different paper folds!)
all_solutions = set()

def recurse(paper: FoldingPaper, depth=0):
    """given a paper, recurse on all papers reachable by one fold (always decreasing paper.length)"""

    if len(paper) == 1:
        all_solutions.add(paper.to_tuple())

    for direction in FoldDirection:
        for i in range(len(paper) - 1):
            paper_copy = paper.copy()
            paper_copy.fold_along(i, direction)
            recurse(paper_copy, depth + 1)


# ---

n = int(input("n: "))
print(f"Calculating with {n=}...")

paper = FoldingPaper(n)
recurse(paper)

print(f"Found {len(all_solutions)} unique permutations")
print(all_solutions)