enum2.ts

enum2.ts

import { range, sum, uniq } from './util';

function paths(s) {
  function swap(s, n) {
    const sc = [].concat(s);
    const tmp = sc[n];
    sc[n] = sc[n + 1];
    sc[n + 1] = tmp;
    return sc;
  }
  const swaps = range(s.length - 1).map(n => s[n] < s[n + 1] ? n : null).filter(x => x != null);
  if (swaps.length == 0)
    return 1;
  else
    return sum(swaps.map(n => paths(swap(s, n))));
}

function flatten<T>(x: T[][]): T[] {
  return [].concat.apply([], x);
}

type Swap = {
  i: number, // index
  n1, n2: number, // numbers involved
};
type Path = Swap[];

// Just actually do the swap
function swap(s: number[], n: number): number[] {
  const sc: number[] = [].concat(s);
  const tmp: number = sc[n];
  sc[n] = sc[n + 1];
  sc[n + 1] = tmp;
  return sc;
}

function epaths(s: number[]): Path[] {
  const swaps: (number | null)[] = range(s.length - 1).map(n => s[n] < s[n + 1] ? n : null)
  const actualSwaps: number[] = swaps.filter(x => x != null);
  if (actualSwaps.length == 0)
    return [[]];
  else {
    const inhs: Path[] = flatten(actualSwaps
      .map(i => epaths(swap(s, i))
        .map(p =>
          [{ i, n1: s[i], n2: s[i + 1] }].concat(p))
      )
    );
    return inhs;
  }
}

function strcmp(a, b) {
  if (a.toString() < b.toString()) return -1;
  if (a.toString() > b.toString()) return 1;
  return 0;
}

function strOfPath(p: Path): string {
  const strs: string[] = p.map(({ i, n1, n2 }) => `${i}-${n1}-${n2}`);
  strs.sort(strcmp);
  return strs.join(",");
}

// OEIS A005118
if (0) {
  for (let N = 1; N < 7; N++) {
    console.log(paths(range(N)));
  }
}

// OEIS A006245
for (let N = 1; N < 7; N++) {
  console.log(uniq(epaths(range(N)).map(strOfPath)).length);
}