"""
p36 — Permutations (LeetCode 46, MEDIUM).

Three implementations:
    permute          — used[]-array backtracking. Default.
    permute_swap     — swap-in-place variant. Mutates and restores input.
    permute_unique   — LC 47, with duplicates via sort + skip.
    permute_brute    — itertools.permutations oracle.

Run: python3 solution.py
"""
from __future__ import annotations
import itertools
import random
from typing import List


# --------------------------------------------------------------------------------------
# Default: used[] backtracking. O(n * n!) time, O(n) recursion + O(n) used[].
# --------------------------------------------------------------------------------------
def permute(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    result: List[List[int]] = []
    used = [False] * n
    path: List[int] = []

    def backtrack() -> None:
        if len(path) == n:
            # INVARIANT: path is a complete permutation; SNAPSHOT (path[:]) because
            # we mutate `path` after returning.
            result.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            # choose
            used[i] = True
            path.append(nums[i])
            backtrack()
            # un-choose
            path.pop()
            used[i] = False

    backtrack()
    return result


# --------------------------------------------------------------------------------------
# Swap-in-place. No used[] array; mutates `nums` and restores via second swap.
# Cannot be cleanly adapted to LC 47 — loses canonical-order info.
# --------------------------------------------------------------------------------------
def permute_swap(nums: List[int]) -> List[List[int]]:
    nums = nums[:]  # don't mutate caller's input
    n = len(nums)
    result: List[List[int]] = []

    def backtrack(start: int) -> None:
        if start == n:
            result.append(nums[:])
            return
        for i in range(start, n):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result


# --------------------------------------------------------------------------------------
# LC 47: Permutations with duplicates. Sort + dedup rule:
#   if i > 0 and a[i] == a[i-1] and not used[i-1]: continue
# --------------------------------------------------------------------------------------
def permute_unique(nums: List[int]) -> List[List[int]]:
    nums = sorted(nums)
    n = len(nums)
    result: List[List[int]] = []
    used = [False] * n
    path: List[int] = []

    def backtrack() -> None:
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            # Canonical-form pruning: among equal values, only consume them in left-to-right
            # order. If the equal-left-sibling is NOT used, choosing nums[i] would generate
            # a permutation already produced (or to be produced) via the sibling.
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


# --------------------------------------------------------------------------------------
# Oracle.
# --------------------------------------------------------------------------------------
def permute_brute(nums: List[int]) -> List[List[int]]:
    return [list(p) for p in itertools.permutations(nums)]


def _canon(perms: List[List[int]]) -> List[tuple]:
    return sorted(tuple(p) for p in perms)


def _canon_unique(perms: List[List[int]]) -> List[tuple]:
    return sorted(set(tuple(p) for p in perms))


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # Empty
    assert permute([]) == [[]]
    assert permute_swap([]) == [[]]
    assert permute_unique([]) == [[]]

    # Single
    assert permute([7]) == [[7]]
    assert permute_swap([7]) == [[7]]

    # Three distinct
    assert _canon(permute([1, 2, 3])) == _canon(permute_brute([1, 2, 3]))
    assert _canon(permute_swap([1, 2, 3])) == _canon(permute_brute([1, 2, 3]))

    # Negatives + zero
    assert _canon(permute([-1, 0, 1])) == _canon(permute_brute([-1, 0, 1]))

    # Duplicates input — permute() returns n! (with duplicates), permute_unique returns unique.
    assert len(permute([1, 1, 2])) == 6
    assert len(permute_unique([1, 1, 2])) == 3
    assert _canon_unique(permute_unique([1, 1, 2])) == _canon_unique(permute_brute([1, 1, 2]))

    # All same
    assert permute_unique([3, 3, 3]) == [[3, 3, 3]]

    # Length 4 unique
    expected_4 = _canon(permute_brute([1, 2, 3, 4]))
    assert _canon(permute([1, 2, 3, 4])) == expected_4
    assert _canon(permute_swap([1, 2, 3, 4])) == expected_4

    # LC 47 size check: [1,1,2,2] has 4!/(2!*2!) = 6 unique permutations
    assert len(permute_unique([1, 1, 2, 2])) == 6

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    # Distinct: permute and permute_swap vs oracle
    for _ in range(150):
        n = rng.randint(0, 5)
        nums = rng.sample(range(-20, 20), n)
        oracle = _canon(permute_brute(nums))
        assert _canon(permute(nums)) == oracle, f"permute disagrees on {nums}"
        assert _canon(permute_swap(nums)) == oracle, f"permute_swap disagrees on {nums}"

    # Duplicates: permute_unique vs deduped oracle
    for _ in range(150):
        n = rng.randint(0, 5)
        nums = [rng.randint(0, 3) for _ in range(n)]
        oracle = _canon_unique(permute_brute(nums))
        got = _canon_unique(permute_unique(nums))
        # also assert no internal duplicates produced
        raw = permute_unique(nums)
        assert len(raw) == len(set(tuple(p) for p in raw)), f"permute_unique produced dupes on {nums}"
        assert got == oracle, f"permute_unique disagrees on {nums}"

    print("stress_test: 300 random inputs (150 distinct, 150 duplicates) — all variants agree with oracle.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")