"""meryemPer vs itertools.permutations: same permutations, same order, timed.

    pip install berkeDet
    python compare_itertools.py        # 10 items:  3,628,800 permutations
    python compare_itertools.py 11     # 11 items: 39,916,800 permutations
                                       # (about a minute and 1.5 GB of memory)

Both methods list every permutation of 0, 1, ..., n-1 in lexicographic order.
The script first checks that the two results are identical, then times them.
berkeDet is free for noncommercial use: https://detsignper.org/python.html
"""
import collections
import itertools
import math
import os
import platform
import sys
import time

import numpy as np

import berkeDet
from berkeDet import meryemPer


def best_time(fn, repeat=3):
    """Best wall-clock time of `repeat` runs, in seconds."""
    best = float("inf")
    for _ in range(repeat):
        start = time.perf_counter()
        fn()
        best = min(best, time.perf_counter() - start)
    return best


def itertools_array(n):
    """itertools.permutations, collected into the same NumPy array."""
    flat = itertools.chain.from_iterable(itertools.permutations(range(n)))
    count = math.factorial(n)
    return np.fromiter(flat, dtype=np.uint8, count=count * n).reshape(count, n)


def itertools_loop_only(n):
    """itertools.permutations, only looped over: nothing is kept.
    (A deque of length 0 consumes the iterator at full C speed.)"""
    collections.deque(itertools.permutations(range(n)), maxlen=0)


n = int(sys.argv[1]) if len(sys.argv) > 1 else 10
if not 2 <= n <= 11:
    sys.exit("Choose n from 2 to 11 (12 items would need about 6 GB per array).")
cores = os.cpu_count() or 1
print(f"berkeDet {berkeDet.__version__} | Python {platform.python_version()} | "
      f"NumPy {np.__version__} | {cores} CPU cores")
print(f"\nAll {math.factorial(n):,} permutations of {n} items, lexicographic order")

# 1. Same result?
same = np.array_equal(itertools_array(n), meryemPer(n))
print("Identical results from itertools and meryemPer:", "YES" if same else "NO")
if not same:
    sys.exit(1)

# 2. Timings
rows = [
    ("itertools.permutations -> NumPy array", lambda: itertools_array(n)),
    ("itertools.permutations, loop only (no array)", lambda: itertools_loop_only(n)),
    ("meryemPer, 1 core", lambda: meryemPer(n, threads=1)),
    (f"meryemPer, all {cores} cores", lambda: meryemPer(n)),
]
times = {}
print(f"\n{'method':<46}{'seconds':>10}")
for label, fn in rows:
    times[label] = best_time(fn)
    print(f"{label:<46}{times[label]:>10.4f}")

ours = times[rows[3][0]]
print(f"\nmeryemPer built the array {times[rows[0][0]] / ours:.0f}x faster than itertools,")
print(f"and {times[rows[1][0]] / ours:.1f}x faster than itertools can merely loop over the permutations.")

# 3. Direct access by rank: a million permutations of 20 items, from rank 10**18
rank = 10**18
start = time.perf_counter()
window = meryemPer(20, start=rank, stop=rank + 1_000_000)
seconds = time.perf_counter() - start
print(f"\n1,000,000 permutations of 20 items starting at rank 10^18, in {seconds:.3f} s:")
print("  first:", window[0].tolist())
print("  last: ", window[-1].tolist())

# itertools can only start from the beginning: measure its speed on 20 items
start = time.perf_counter()
collections.deque(itertools.islice(itertools.permutations(range(20)), 2_000_000), maxlen=0)
per_second = 2_000_000 / (time.perf_counter() - start)
years = rank / per_second / (365.25 * 24 * 3600)
print(f"itertools would first have to step through 10^18 permutations:"
      f" about {years:,.0f} years at its speed measured here.")