permute_inplace.py

# Demo of finding the nth permutation of a list in-place in Python >=3.8
# Copyright (c) 2023 Sebastian Pipping <[email protected]>
# SPDX-License-Identifier: GPL-3.0-or-later

from copy import copy
from math import factorial
from typing import List
from unittest import TestCase, TestLoader, TextTestRunner


def permute_inplace(permutation: int, values: List):
    for target_index in range(len(values)):
        choices_count = len(values) - target_index
        source_index = permutation % choices_count + target_index
        if source_index != target_index:
            # Swap
            values[target_index], values[source_index] = (
                values[source_index],
                values[target_index],
            )
        permutation //= choices_count


class PermuteTest(TestCase):
    original = list(range(6))
    permutations_count = factorial(len(original))

    def test_no_overlaps(self):
        permutations = set()

        for i in range(self.permutations_count):
            clone = copy(self.original)
            permute_inplace(i, clone)
            permutations.add(str(clone))

        self.assertEqual(len(permutations), self.permutations_count)

    def test_ring_property(self):
        for i in range(self.permutations_count):
            clone_a = copy(self.original)
            clone_b = copy(self.original)

            permute_inplace(0 - i, clone_a)
            permute_inplace(self.permutations_count - i, clone_b)

            self.assertEqual(clone_b, clone_a)


if __name__ == "__main__":
    test_suite = TestLoader().loadTestsFromTestCase(PermuteTest)
    TextTestRunner(verbosity=2).run(test_suite)