import numpy as np
import random
import time

def meryemSign(n):
    b = [1]
    for e in range(1, n):
        c = b[:]
        for d in range(e):
            if d % 2 == 0:
                f = [-x for x in c]
            else:
                f = c[:]
            b.extend(f)
    return b

def meryemPer(n):
    a = [[1]]
    for b in range(2, n + 1):
        c = list(range(1, b + 1))
        d = []
        for f in c:
            g = [e for e in c if e != f]
            for h in a:
                j = [g[i - 1] for i in h]
                d.append([f] + j)
        a = d
    return a

def berkeDet(matrix):
    n = len(matrix)
    signs = meryemSign(n)
    perms = meryemPer(n)
    det = 0
    for sign, perm in zip(signs, perms):
        product = 1
        for i in range(n):
            product *= matrix[i][perm[i] - 1]
        det += sign * product
    return det

# Also verify meryemPer produces lexicographic order and meryemSign matches inversion-count signs
def inversion_sign(perm):
    m = 0
    n = len(perm)
    for i in range(n):
        for j in range(i+1, n):
            if perm[i] > perm[j]:
                m += 1
    return 1 if m % 2 == 0 else -1

random.seed(42)
print("=" * 70)
print("VERIFICATION: berkeDet vs numpy.linalg.det, n = 1 .. 10")
print("=" * 70)

results = []
for n in range(1, 11):
    # random integer matrix, entries in [-9, 9]
    M = [[random.randint(-9, 9) for _ in range(n)] for _ in range(n)]
    t0 = time.time()
    bd = berkeDet(M)
    t1 = time.time()
    npd = np.linalg.det(np.array(M, dtype=float))
    rel_err = abs(bd - npd) / max(1.0, abs(npd))
    ok = rel_err < 1e-9
    results.append((n, bd, npd, rel_err, ok, t1 - t0))
    print(f"n={n:2d}  berkeDet={bd:>18}  numpy={npd:>22.6f}  rel_err={rel_err:.2e}  {'OK' if ok else 'FAIL'}  ({t1-t0:.2f}s)")

print()
print("=" * 70)
print("STRUCTURAL CHECK: lexicographic order + sign correctness, n = 1 .. 8")
print("=" * 70)
import itertools
for n in range(1, 9):
    perms = meryemPer(n)
    signs = meryemSign(n)
    ref = [list(p) for p in itertools.permutations(range(1, n + 1))]
    lex_ok = perms == ref
    sign_ok = all(s == inversion_sign(p) for s, p in zip(signs, perms))
    print(f"n={n}: lexicographic order {'OK' if lex_ok else 'FAIL'}, signs {'OK' if sign_ok else 'FAIL'} ({len(perms)} permutations)")

print()
print("All verification complete.")