Permutations in JavaScript?

Efficient duplication avoidance

Got duplicate elements in the mix? Let's whip up a set to achieve unique permutations:

function permuteUnique(arr) {
  const result = [];
  const swap = (a, i, j) => ([a[i], a[j]] = [a[j], a[i]]);
  const generate = (k, heapArr) => {
    if (k === 1) {
      const permutationStr = JSON.stringify(heapArr);
      if (!result.includes(permutationStr)) {
        result.push(permutationStr); // No pushing duplicates, please
      }
      return;
    }
    generate(k - 1, heapArr);
    for (let i = 0; i < k - 1; i++) {
      swap(heapArr, k % 2 ? 0 : i, k - 1);
      generate(k - 1, heapArr);
    }
  };
  generate(arr.length, arr.slice());
  return result.map(JSON.parse); 
}

console.log(permuteUnique([1, 1, 2])); // No duplicates allowed, thank you!


This recipe prevents permutations from repeating themselves by stringifying each array and efficiently filtering out any déjà vu.

Spacewise efficiency with generators

As the permutations explode with larger sets, a generator function comes to rescue to yield permutations one by one, thus achieving spatial thriftiness of O(N):

function* permuteGenerator(arr) { // One permutation at a time, please
  function* doGenerate(k, heapArr) {
    if (k === 1) {
      yield heapArr.slice();
    } else {
      yield* doGenerate(k - 1, heapArr);
      for (let i = 0; i < k - 1; i++) {
        swap(heapArr, k % 2 ? 0 : i, k - 1);
        yield* doGenerate(k - 1, heapArr);
      }
    }
  }
  yield* doGenerate(arr.length, arr.slice());
}

const generator = permuteGenerator([1, 2, 3]); // Firing up the generator
for (let permutation of generator) {
  console.log(permutation); // One at a time now, folks
}


Efficiency is key in Grand Permutations Carnival, especially in juggling heavier computations where all permutations at once are but a dream.

Visualization: all stories that can be told

Take a step back and picture permutations as different ways to arrange some items:

Given Items: [🍎, 🍌, 🍍]

Each arrangement tells its own story:

Arrangement	Story
1	🍎🍌🍍
2	🍎🍍🍌
3	🍌🍎🍍
4	🍌🍍🍎
5	🍍🍎🍌
6	🍍🍌🍎

Permutations = Every story that can be told with given elements. 📚✨

The art of handling edge cases

Building a truly reliable implementation includes handling edge cases and foreseeing Murphy's Law in action:

• Empty arrays: If it's empty in, it's empty out.
• Single-element arrays: Single is cool, but don't forget to wrap it with an array.
• Non-array inputs: Check your inputs, or face the TypeError wrath!

These measures will keep your function robust and the errors at bay.

Mathematics cometh to the rescue

Venture beyond recursion and delve into mathematical combinatorics for alternative permutation solutions. Key unlockers here are factorials and power sets for those who speak Math.

Optimizeth thou permutations

Layeth the foundation of permutations, thou may have, but the realm of optimization awaiteth:

• Perform in-place swaps to help with memory economization.
• Realize lazy evaluation and compute permutations just when they're needed.
• Cache your findings for subsequences that frequent your calculations.
• Contemplate iterative solutions to restrain the stack overflow beast for very large sets.

Trust, but verify: robust testing

No quest for permutations is completed without ample testing:

• Short, simple arrays for the basics.
• Large arrays for performance pressure tests.
• Arrays with the complexity of various data types.

Only the array that crosses these tests is the one true robust permutation array.

The power of ES6 on display

Unleash the wizardry of ES6 features for a legible and concise code sheet. The spread operators, arrow functions, and flatMap methods not only bring conciseness but also are potential performance boosters in your permutation voyage.

Clear view to permutations with printing

When inspecting or showcasing your permutations, clean printing is your friend:

console.log(result.map(permutation => JSON.stringify(permutation)).join('\n'));


This prints arrays as distinct lines, aiding in debugging and showcasing your permutation playground!

Broadening the horizon

Heap's algorithm surely is a gallant knight, but remember, other algorithms also dance the permutation ballet. So venture on, explorer! Your perfect algorithm might be just around the corner. Always remember, performance, readability, and utility maketh the king!