A solution to a problem with permutations in array

permutations-in-array.js

/*
// Camilo Castro <camilo@ninjas.cl>

Problem:
Given a numeric array. find the cardinality of the set where substracting (absolute)
every number pair inside the set, results 1, 0 or less.

Example:
array = [ 1,1,2,2,4,4,5,5,5]

// length 4
// 1 - 1 = 0; 1 - 2 = 0;
subset1 = [1, 1, 2, 2]

// length 5
// 4 - 5 = 1
subset2 = [4,4,5,5,5]

subset2 have the greatest length (5).
The answer is 5.

Restrictions:

2 <= array.length <= 100
0 < array[i] < 100
answer should be >= 2

*/

(async () => {
  // Use heap algorithm to generate permutations
  // O(n!) runtime complexity
  // O(n) space complexity
  // http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf
  const getPermutations = async (elements, callback) => {
    // this function is based on the code provided by @paulrohan
    // https://medium.com/@paulrohan/implemetning-heap-algorithm-to-find-permutation-of-a-set-of-numbers-in-javascript-d6b6ef8ee0e

    const swap = (array, initial, last) => {
      const temp = array[initial];
      array[initial] = array[last];
      array[last] = temp;
      return array;
    };

    // Use memoization to improve the algorithm perfomance
    // (dynamic programming)
    const memoize = {};

    const permute = async (array, callback, length) => {
      // set length default to array.length
      length = length || array.length;

      const key = String(array);

      if (length === 1) {
        // reached base case
        // memoize result (dynamic programming)
        // and execute callback
        // [...array] this is needed to create a strong reference and not to overwrite the current value with the last value obtained.
        memoize[key] = [...array];
        return callback(memoize[key]);
      }

      if (memoize[key]) {
        // we already found this value
        return callback(memoize[key]);
      }

      const last = length - 1;
      let current = 0;
      for (let index = 1; index <= length; index++) {
        // recursively check possible permutations
        // only stop when n = 1
        // and save the result
        permute(array, callback, last);

        // when length is odd so n % 2 is 1,
        // select the first number, then the second number,
        // then the third number to be swapped with the last number
        current = index - 1;

        // when length is even so n % 2 is 0,
        // always select the first number with the last number
        if (length % 2 == 0) {
          current = 0;
        }

        // swap the elements of the array
        // the current index, with the last (length - 1)
        // note we are using a by ref array
        // the swap function will modify it
        swap(array, current, last);
      }
    };

    // Using Heap Algorithm + Memoization to Permute
    return permute(elements, callback);
  };

  const isValid = (candidate) => {
    // Iterate over all the candidate elements
    // and implement the logic to validate them
    // O(n)
    if (candidate.length < 2) {
      return false;
    }

    // O(n * n)
    // Turtle and hare strategy
    // We have a slow pointer (turtle)
    // and a fast pointer (hare)
    // make the validations for each case
    let current = null;
    let next = null;
    let diff = null;
    let valid = false;
    for (i = 0; i < candidate.length; i++) {
      for (j = 0; j < candidate.length; j++) {
        current = candidate[i]; // turtle
        next = candidate[j]; // hare
        diff = Math.abs(current - next);
        valid = diff <= 1;

        if (!valid) {
          return false;
        }
      }
    }
    return true;
  };

  const getPermutationsInSubsets = async (elements) => {
    // first we get all the possible permutations with the initial elements
    // and filter out the duplicates.
    const unique = {};
    getPermutations(elements, (permutation) => {
      const key = String(permutation);
      unique[key] = permutation;
    });

    // then we begin to create subset of each permutation possibility
    // by shortening the element array until we got subset of 2 elements
    // filter out the duplicates too
    const subsets = {};
    for (const key in unique) {
      const set = unique[key];
      let length = set.length;
      // Example [4, 5, 6, 7] cardinality 4
      while (length >= 2) {
        const subitems = set.slice(0, length);
        // Example [4,5,6,7] -> [4,5,6] -> [4,5]
        // filter out duplicates
        subsets[String(subitems)] = subitems;
        length--;
      }
    }

    // Example
    // [4, 5, 6, 7] -> [4,5,6] -> [4,5] // duplicate
    // [4, 5, 7, 6] -> [4,5,7] -> [4,5]
    // [4, 7, 5, 6] -> [4,7,5] -> [4,7]
    // 8 candidates

    // now we filter out all the subsets that have the same
    // length as the initial elements, since we already check that case.
    // and sort the cases from greater length to lesser length (DESC).

    // Example
    // original: [4, 5, 6, 7]
    // all the possible permutations with the same length
    // will be invalid (https://en.wikipedia.org/wiki/Commutative_property). So we can safely remove them
    // from the pool of candidates.
    // (invalid) [4, 5, 6, 7] -> (valid) [4,5,6]
    // (invalid) [4, 5, 7, 6] -> (valid) [4,5,7] -> (valid) [4,5]
    // (invalid) [4, 7, 5, 6] -> (valid) [4,7,5] -> (valid) [4,7]
    // 5 candidates

    const candidates = Object.values(subsets)
      .filter((subset) => subset.length != elements.length)
      .sort((a, b) => a.length < b.length);

    // time to check if all the candidates match the requirements
    // since they are ordered in DESC order the first match
    // with a possitive result would be the largest possibility
    // and we do not need to check the other candidates.
    // we can get our result.
    let chosen = [];
    for (const candidate of candidates) {
      if (isValid(candidate)) {
        chosen = candidate;
        break;
      }
    }

    return { result: chosen.length, candidate: chosen };
  };

  const solution = async (input) => {
    const error = new Error("No candidates found.");
    if (input.length < 2) {
      return error;
    }

    // check the maximum possible escenario first
    // this is important because if this is not valid
    // then all the other permutations with the same
    // length would also be invalid.
    // but we still need those permutations in order
    // to generate all the possible solution candidates
    // by trimming their length.
    if (isValid(input)) {
      return { result: input.length, candidate: input, input };
    }

    const result = await getPermutationsInSubsets(input);

    if (result.candidate.length > 1) {
      return { input, ...result };
    }

    return error;
  };

  // https://www.glc.us.es/~jalonso/vestigium/el-metodo-de-polya-para-resolver-problemas/
  // https://www.cs.kent.ac.uk/people/staff/sjt/Haskell_craft/HowToProgIt.html
  const main = async () => {
    const inputs = [
      [4, 6, 5, 3, 3, 1], // solution 3
      [1, 1, 2, 2, 4, 4, 5, 5, 5], // solution 5
      [1, 2, 3], // solution [1,2] length = 2
      [4, 1], // error
    ];

    for (const input of inputs) {
      console.log("process", input);
      const result = await solution(input);
      console.log(result);
    }
  };

  await main();
  console.log("Done");
})();