# ===================================================================== # meryemSign ISOLATED BENCHMARK — Google Colab edition # Question: how fast can you produce the signs sgn(sigma) of ALL n! # permutations of {1..n} IN LEXICOGRAPHIC ORDER? # # Permutation generation is NOT what we measure here. The classical # baselines are even given their permutations by C-speed # itertools.permutations (streamed, near-free), so every Python-level # cost they pay is pure SIGN cost. meryemSign needs no permutations # at all -- that is precisely its point. # # CONTESTANTS # 1. meryemSign block replication + flips; MATERIALIZES # all n! signs; no permutations touched. # 2. inv-count (stream) itertools perms + O(n^2) inversion count # per permutation. The textbook method. # 3. merge-count (stream) itertools perms + O(n log n) merge-based # inversion parity per permutation. # 4. Narayana + O(1) flip steps lexicographic perms in place and # updates parity per step from the step's # own structure (1 swap + floor(L/2) # reversal transpositions). The strongest # classical baseline: O(1) sign per step, # lexicographic, O(n) memory. # # Every method returns (sum of signs, count of +1). For n>=2 the sum # must be 0 and the +1 count must be n!/2 -- built-in sanity. Deeper # verification below compares actual sign sequences. # # HOW TO USE ON COLAB: CPU runtime. Paste, run. Edit CONFIG to push. # Memory: only meryemSign materializes. n! signs as a Python list: # n=11 ~0.4 GB n=12 ~4.6 GB (needs standard Colab) n=13 ~55 GB (no) # ===================================================================== import gc, time, math, statistics, itertools, random # ----------------------------- CONFIG -------------------------------- RUNS = 3 N_MIN = 7 MAX_N = { "meryemSign": 12, # memory-guarded; 12 fits Colab "inv-count (stream)": 11, # n=12 -> roughly 20-30 min "merge-count (stream)": 11, # n=12 -> similar order "Narayana + O(1) flip": 12, # cheap; 12 -> a few minutes } VERIFY_FULL_UPTO = 10 # exhaustive sequence comparison up to here SPOT_CHECKS = 200 # random-rank checks for n above that SEED = 7 # --------------------------- 1. meryemSign --------------------------- def meryemSign(n): b = [1] for e in range(1, n): c = b[:] for d in range(e): f = [-x for x in c] if d % 2 == 0 else c[:] b.extend(f) return b def run_meryemSign(n): b = meryemSign(n) return sum(b), b.count(1) # ------------------- 2. inversion count (streaming) ------------------ def inv_sign(p): m = 0; n = len(p) for i in range(n): pi = p[i] for j in range(i + 1, n): if pi > p[j]: m += 1 return 1 - 2 * (m & 1) def run_invcount(n): total = 0; plus = 0 for p in itertools.permutations(range(n)): s = inv_sign(p) total += s if s == 1: plus += 1 return total, plus # ---------------- 3. merge-based parity (streaming) ------------------ def merge_parity(p): """Number of inversions mod 2 via merge sort; returns sign.""" a = list(p) tmp = [0] * len(a) inv = 0 width = 1 n = len(a) while width < n: for lo in range(0, n, 2 * width): mid = min(lo + width, n) hi = min(lo + 2 * width, n) i, j, k = lo, mid, lo while i < mid and j < hi: if a[i] <= a[j]: tmp[k] = a[i]; i += 1 else: tmp[k] = a[j]; j += 1 inv += mid - i k += 1 while i < mid: tmp[k] = a[i]; i += 1; k += 1 while j < hi: tmp[k] = a[j]; j += 1; k += 1 a[lo:hi] = tmp[lo:hi] width *= 2 return 1 - 2 * (inv & 1) def run_mergecount(n): total = 0; plus = 0 for p in itertools.permutations(range(n)): s = merge_parity(p) total += s if s == 1: plus += 1 return total, plus # ----------- 4. Narayana stepping with O(1) parity update ------------ def run_narayana_flip(n, collect=None): """Lexicographic stepping; sign updated from step structure: one swap (1 transposition) + suffix reversal (L//2 transpositions). Strongest classical baseline. O(n) memory.""" p = list(range(n)) sign = 1 total = 0; plus = 0 while True: total += sign if sign == 1: plus += 1 if collect is not None: collect.append(sign) i = n - 2 while i >= 0 and p[i] >= p[i + 1]: i -= 1 if i < 0: return total, plus j = n - 1 while p[j] <= p[i]: j -= 1 p[i], p[j] = p[j], p[i] p[i + 1:] = p[:i:-1] L = n - 1 - i # reversed-suffix length t = 1 + (L >> 1) # transpositions this step if t & 1: sign = -sign # ------------------------- verification ------------------------------ def kth_lex_perm(n, k): """k-th (0-based) lexicographic permutation via factoradic.""" elems = list(range(n)); out = [] for i in range(n, 0, -1): f = math.factorial(i - 1) idx, k = divmod(k, f) out.append(elems.pop(idx)) return out def verify(n): b = meryemSign(n) fact = math.factorial(n) assert len(b) == fact assert sum(b) == (1 if n == 1 else 0) assert b.count(1) == (1 if n == 1 else fact // 2) if n <= VERIFY_FULL_UPTO: for idx, p in enumerate(itertools.permutations(range(n))): assert b[idx] == inv_sign(p), f"n={n} mismatch at rank {idx}" coll = [] run_narayana_flip(n, collect=coll) assert coll == b, f"n={n}: Narayana-flip sequence differs" return f"n={n}: FULL verification OK ({fact} signs, 3-way match)" else: rng = random.Random(SEED) for _ in range(SPOT_CHECKS): k = rng.randrange(fact) assert b[k] == inv_sign(kth_lex_perm(n, k)), \ f"n={n} spot-check failed at rank {k}" return (f"n={n}: checksum OK + {SPOT_CHECKS} random-rank " f"spot checks OK") # ----------------------- memory guard -------------------------------- def meryem_mem_gb(n): f = math.factorial(n) return (f * 8 + 2 * math.factorial(n - 1) * 8) / 1e9 def available_ram_gb(): try: import psutil return psutil.virtual_memory().available / 1e9 except Exception: return None # ---------------------------- benchmark ------------------------------- methods = [ ("meryemSign", run_meryemSign), ("inv-count (stream)", run_invcount), ("merge-count (stream)", run_mergecount), ("Narayana + O(1) flip", run_narayana_flip), ] N_TOP = max(MAX_N.values()) print(f"{'n':>3} | " + " | ".join(f"{name:>22}" for name, _ in methods)) print("-" * (6 + 25 * len(methods))) results = {name: {} for name, _ in methods} for n in range(N_MIN, N_TOP + 1): ref = None row = [] for name, fn in methods: if n > MAX_N[name]: row.append(None); continue if name == "meryemSign": need = meryem_mem_gb(n); avail = available_ram_gb() if avail is not None and need > 0.7 * avail: print(f" [meryemSign n={n}: needs ~{need:.1f} GB, " f"~{avail:.1f} GB available -> SKIPPED]") row.append(None); continue times = [] for _ in range(RUNS): gc.collect() t0 = time.perf_counter() out = fn(n) t1 = time.perf_counter() times.append(t1 - t0) if ref is None: ref = out assert out == ref, f"CHECKSUM MISMATCH {name} n={n}" med = statistics.median(times) results[name][n] = med row.append(med) print(f"{n:>3} | " + " | ".join( (f"{t:>20.4f}s" if t is not None else f"{'-':>21}") for t in row)) print("\nCorrectness:") for n in range(N_MIN, min(N_TOP, max(MAX_N['meryemSign'], 0)) + 1): if n in results["meryemSign"]: print(" " + verify(n)) print("\nmeryemSign speedups:") for n in sorted(results["meryemSign"]): t = results["meryemSign"][n] parts = [f"n={n}:"] for name in ("inv-count (stream)", "merge-count (stream)", "Narayana + O(1) flip"): if n in results[name]: parts.append(f"vs {name}: {results[name][n]/t:.2f}x") print(" " + " ".join(parts)) try: import matplotlib.pyplot as plt plt.figure(figsize=(8, 5)) for name, _ in methods: xs = sorted(results[name]) if xs: plt.plot(xs, [results[name][x] for x in xs], marker="o", label=name) plt.yscale("log"); plt.xlabel("n") plt.ylabel("seconds for all n! signs (log)") plt.title("Sign generation only, lexicographic order (pure Python)") plt.grid(True, which="both", alpha=0.3); plt.legend(); plt.show() except Exception as e: print(f"(plot skipped: {e})")