groundhog_sort.py

gistfile1.txt

from itertools import permutations
from typing import Iterable, TypeVar

T = TypeVar("T")


def groundhog_sort(values: Iterable[T]) -> list[T]:
    """
    Sort by regenerating every permutation from scratch
    for each position in the output.
    """
    items = tuple(values)
    result: list[T] = []

    for position in range(len(items)):
        smallest: T | None = None
        found_candidate = False

        # Groundhog Day: generate every permutation all over again.
        for permutation in permutations(items):
            prefix_matches = True

            for prefix_index in range(position):
                if permutation[prefix_index] != result[prefix_index]:
                    prefix_matches = False
                    break

            if not prefix_matches:
                continue

            candidate = permutation[position]

            if not found_candidate or candidate < smallest:
                smallest = candidate
                found_candidate = True

        if not found_candidate:
            raise RuntimeError("No permutation matched the selected prefix")

        result.append(smallest)

    return result


numbers = [4, 2, 5, 1, 3]

print("Input: ", numbers)
print("Sorted:", groundhog_sort(numbers))