find index of n-th permutation without iterating over previous permutations (lexicographical ordered, repeatable values)

permutation.ts

//////////////////
//
// find index of n-th permutation without iterating over previous permutations
// - lexicographical ordered
// - repeatable values
//
//////////////////
import Decimal from "decimal.js";

Decimal.set({ precision: 1000, rounding: 1 });

// https://stackoverflow.com/a/50605052
// Convert from C# example
// extended for use with arbitrary precision numbers via Decimal.js
// C# - factorial limited up to 20 digits, and 18 digits in javascript version via int
// with Decimal.js factorial almost "unlimited"
class PermutationOuelletLexico3 {
  private _sortedValues: string | any[];
  private _sortedValuesLength: Decimal;
  private _valueUsed: any;
  private maxIndex: Decimal;
  private _result: any;

  constructor(sortedValues: string[]) {
    if (sortedValues.length <= 0) {
      throw new Error("sortedValues.Lenght should be greater than 0");
    }

    this._sortedValues = sortedValues;
    this._sortedValuesLength = new Decimal(this._sortedValues.length);
    this.result = new Array(this._sortedValues.length);
    this._valueUsed = new Array(this._sortedValues.length).fill(false);

    this.maxIndex = this.factorial(this._sortedValuesLength);
  }

  // ************************************************************************
  get result() {
    return this._result;
  }

  set result(value) {
    this._result = value;
  }

  factorial(n: Decimal): Decimal {
    if (n.eq(0)) {
      return new Decimal(1);
    }
    return n.mul(this.factorial(n.minus(1)));
  }
  // ************************************************************************
  /// <summary>
  /// Return the permutation relative to the index received, according to _sortedValues.
  /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
  /// </summary>
  /// <param name="sortIndex"></param>
  /// <param name="result">Value is not used as input, only as output. Re-use buffer in order to save memory</param>
  /// <returns></returns>
  getValuesForIndex(sortIndex: string) {
    const size = this._sortedValues.length;
    const _size = new Decimal(this._sortedValues.length);
    const _sortIndex = new Decimal(sortIndex);

    if (_sortIndex.lessThan(0)) {
      throw new Error("sortIndex should be greater or equal to 0.");
    }

    if (_sortIndex.greaterThanOrEqualTo(this.maxIndex)) {
      throw new Error(
        "sortIndex should be less than factorial(the lenght of items)"
      );
    }

    for (let n = 0; n < this._valueUsed.length; n++) {
      this._valueUsed[n] = false;
    }

    let factorielLower = new Decimal(this.maxIndex);

    for (let index = 0; index < size; index++) {
      let factorielBigger = new Decimal(factorielLower);
      factorielLower = this.factorial(_size.minus(1).minus(index));
      let resultItemIndex = _sortIndex.mod(factorielBigger).div(factorielLower);
      let correctedResultItemIndex = 0;
      // eslint-disable-next-line prettier/prettier
      for (; ;) {
        if (!this._valueUsed[correctedResultItemIndex]) {
          resultItemIndex = resultItemIndex.minus(1);
          if (resultItemIndex.lessThan(0)) {
            break;
          }
        }
        correctedResultItemIndex++;
      }

      this.result[index] = this._sortedValues[correctedResultItemIndex];
      this._valueUsed[correctedResultItemIndex] = true;
    }
  }

  // ************************************************************************
  /// <summary>
  /// Calc the index, relative to _sortedValues, of the permutation received
  /// as argument. Returned index is 0 based.
  /// </summary>
  /// <param name="values"></param>
  /// <returns></returns>
  getIndexOfValues(values: string[]): string {
    const size = this._sortedValues.length;
    const _size = new Decimal(this._sortedValues.length);
    let valuesIndex = "0";

    let valuesLeft = [...this._sortedValues];

    for (let index = 0; index < size; index++) {
      let indexFactorial = this.factorial(_size.minus(1).minus(index));

      let value = values[index];
      let indexCorrected = valuesLeft.indexOf(value);
      valuesIndex = new Decimal(valuesIndex)
        .plus(new Decimal(indexCorrected).mul(indexFactorial))
        .toFixed();
      valuesLeft.splice(indexCorrected, 1);
    }
    return valuesIndex;
  }
}

const value = "ACBD1123ACBD1123";
const permutator = new PermutationOuelletLexico3(value.split("").sort());
const index = permutator.getIndexOfValues(value.split(""));
permutator.getValuesForIndex(index);

console.log({
  permutator,
  value_len: value.length,
  // value_len_div2: value.length / 2,
  value,
  index,
  // index_hex: new Decimal(index).toHex(),
  // index_hex_len: new Decimal(index).toHex().split("x")[1].length / 2,
  eq: value === permutator.result.join(""),
});

///////////////////

// let w = new Decimal(index);
// let ctr = new Decimal(100000000);

// console.log("estimate", w, w.div(ctr).round().toFixed());

// while (!w.eq(0)) {
//   w = w.minus(1);
//   if (w.mod(ctr).round().toFixed() === "1") {
//     console.log(w.toFixed(), w.div(ctr).toFixed(), ctr.toFixed());
//   }
// }

///////////////////

// let w = 11481669223056;
// let ctr = 100000000;

// console.log("estimate", w / ctr);

// while (w !== 0) {
//   w--;
//   if (w % ctr === 1) console.log(w / ctr, ctr);
// }

// eslint-disable-next-line prettier/prettier
export { };