// Core combinatorics for covering designs C(v,k,t).
// Points are 0..v-1. A block is a sorted array of k point-ids.
// t-subsets are indexed 0..C(v,t)-1 in colex order via rank/unrank.

export function binom(n, r) {
  if (r < 0 || r > n) return 0;
  r = Math.min(r, n - r);
  let x = 1;
  for (let i = 1; i <= r; i++) x = x * (n - r + i) / i;
  return Math.round(x);
}

// Rank a t-subset (sorted array) in colex order: sum over elements C(x_i, i+1)
export function colexRank(subset) {
  let s = 0;
  for (let i = 0; i < subset.length; i++) s += binom(subset[i], i + 1);
  return s;
}

export function colexUnrank(rank, t) {
  const subset = new Array(t);
  let r = rank;
  let prev = Infinity;
  for (let i = t; i >= 1; i--) {
    let x = i - 1;
    while (x + 1 < prev && binom(x + 1, i) <= r) x++;
    subset[i - 1] = x;
    r -= binom(x, i);
    prev = x;
  }
  return subset;
}

export function* tSubsetIter(v, t) {
  const s = Array.from({ length: t }, (_, i) => i);
  while (true) {
    yield s.slice();
    let i = t - 1;
    while (i >= 0 && s[i] === v - t + i) i--;
    if (i < 0) return;
    s[i]++;
    for (let j = i + 1; j < t; j++) s[j] = s[j - 1] + 1;
  }
}

export function* kBlockIter(v, k) { yield* tSubsetIter(v, k); }

// Precompute for each block id the list of t-subset ids it covers.
export function buildCoverageTable(v, k, t) {
  const numBlocks = binom(v, k), numT = binom(v, t);
  const cov = new Array(numBlocks);
  const buf = new Array(t);
  const block = new Array(k);
  for (const b of kBlockIter(v, k)) {
    const id = colexRank(b);
    const list = [];
    // enumerate all t-subsets of this block
    const idx = Array.from({ length: t }, (_, i) => i);
    while (true) {
      for (let i = 0; i < t; i++) buf[i] = b[idx[i]];
      list.push(colexRank(buf));
      let i = t - 1;
      while (i >= 0 && idx[i] === k - t + i) i--;
      if (i < 0) break;
      idx[i]++;
      for (let j = i + 1; j < t; j++) idx[j] = idx[j - 1] + 1;
    }
    cov[id] = list;
  }
  return { cov, numBlocks, numT };
}

// Verify: returns {valid, uncovered: count of uncovered t-subsets, minMultiplicity}
export function verifyCovering(v, k, t, blocks) {
  const numT = binom(v, t);
  const c = new Uint8Array(numT); // multiplicity may exceed 255? cap fine for our sizes
  for (const b of blocks) {
    if (!Array.isArray(b) || b.length !== k) throw new Error(`bad block length ${JSON.stringify(b).slice(0,50)}`);
    for (let i = 0; i < k; i++) {
      if (!(Number.isInteger(b[i]) && b[i] >= 0 && b[i] < v)) throw new Error('block point out of range');
      if (i > 0 && b[i] <= b[i - 1]) throw new Error('block not strictly ascending');
    }
    const idx = Array.from({ length: t }, (_, i) => i);
    const buf = new Array(t);
    while (true) {
      for (let i = 0; i < t; i++) buf[i] = b[idx[i]];
      c[colexRank(buf)]++;
      let i = t - 1;
      while (i >= 0 && idx[i] === k - t + i) i--;
      if (i < 0) break;
      idx[i]++;
      for (let j = i + 1; j < t; j++) idx[j] = idx[j - 1] + 1;
    }
  }
  let uncovered = 0, minMult = Infinity;
  for (let x = 0; x < numT; x++) {
    if (c[x] === 0) uncovered++;
    if (c[x] < minMult) minMult = c[x];
  }
  return { valid: uncovered === 0, uncovered, minMult };
}

export function schonheimLower(v, k, t) {
  let val = 1;
  for (let i = t - 1; i >= 0; i--) val = Math.ceil((v - i) / (k - i) * val);
  return val;
}

// Format helpers matching the bounty's text format
export function fmtBlock(b) { return b.join(' '); }
export function parseBlock(line) { return line.trim().split(/\s+/).map(Number); }

// Apply permutation p (array mapping old->new) to block
export function applyPerm(block, p) {
  const b = block.map(x => p[x]);
  b.sort((a, c) => a - c);
  return b;
}

// Orbit of block under group gens (array of permutations), BFS
export function orbitOf(block, gens) {
  const seen = new Map();
  const start = block.slice();
  const q = [start];
  seen.set(start.join(','), start);
  while (q.length) {
    const cur = q.pop();
    for (const g of gens) {
      const nb = applyPerm(cur, g);
      const key = nb.join(',');
      if (!seen.has(key)) { seen.set(key, nb); q.push(nb); }
    }
  }
  return [...seen.values()];
}