ANDSiblings.js

"use strict";

const MAX_ARRAY_LENGTH = 2 ** 32 - 1;


/**
 * Insertion sort FTW
 * @param str {string}
 * @param limit {number}
 * @returns {number[]|undefined}
 */
function getDescendingDigits (str, limit = MAX_ARRAY_LENGTH) {
  if  (limit < 1 || str.length < 2)
    return;

  const output = [],
        strLength = str.length;
  let outputLength = 0,
      max = -1,
      min = 10;

  for (let i = 0; i < strLength; ++i) {
    const charCode = str.charCodeAt(i);

    // charCode of 0 is 48
    if (48 <= charCode && charCode < 58) {
      const digit = charCode - 48;

      if (max <= digit) {
        max = digit;
        outputLength = output.unshift(digit);
      } else if (min >= digit) {
        min = digit;
        outputLength = output.push(digit);
      } else {
        const spliceIndex = output.findIndex(n => n < digit);
        output.splice(spliceIndex, 0, digit);
        ++outputLength;
      }

      if (outputLength === limit)
        break;
    }
  }

  return output;
}

/**
 * Adapted from "[The Next Number Problem]{@link http://wordaligned.org/articles/next-permutation#tocwhats-happening-here}"
 * NOT in-place.
 * @param digits {number[]}
 * @returns {number[]}
 */
function findNextSmallest (digits) {
  const digitsLength = digits.length;

  if (digitsLength < 2)
    return digits; // /!\ By reference!

  let tailIndex;

  // Longest _increasing_ tail
  for (tailIndex = digitsLength - 1; tailIndex > 0; --tailIndex) {
    if (digits[tailIndex] < digits[tailIndex - 1])
      break;
  }

  // Already the smallest number
  if (tailIndex === 0)
    return digits; // /!\ By reference!

  const lastNOfHead = digits[tailIndex - 1];

  let indexOfSmaller;

  // We are interested in the first number _smaller_ than the head
  for (indexOfSmaller = digitsLength - 1; indexOfSmaller > tailIndex; --indexOfSmaller) {
    if (digits[indexOfSmaller] < lastNOfHead)
      break;
  }

  const output = digits.slice(0, tailIndex - 1);

  // Swap the smaller (...)
  output.push(digits[indexOfSmaller]);

  // Reverse the tail
  for (let i = digitsLength - 1; i >= tailIndex; --i) {
    output.push(
      // (...) with the head
      i === indexOfSmaller
        ? lastNOfHead
        : digits[i]
    );
  }

  return output;
}

/**
 *
 * @generator
 * @param str {string}
 * @yields {number[]>}
 */
function *genANDSiblingsDescending (str) {
  for (
    let newPerm = getDescendingDigits(str, 3), lastPerm;
    newPerm !== lastPerm;
    newPerm = findNextSmallest(lastPerm)
  ) {
    yield newPerm;
    lastPerm = newPerm;
  }
}

for (const n of genANDSiblingsDescending("A 3B2 C6D"))
  console.log(n);