Getting back to the job market means I had to do endless Data Structure and Algorithms (DSA) questions again. Although I was pretty confident with my nested for loops skills, I get stuck at the following question:

Generate a sorted permutation from an array of numbers.

Example 1:

• input: [1,2]
• output: [[1,2],[2,1]]

Example 2:

• input: [2,5,8]
• output: [[2,5,8],[2,8,5],[5,2,8],[5,8,2],[8,2,5],[8,5,2]]

I knew very well there should be n! combinations, but generating them is another issue. The interviewer didn't allow me to use search engine this time. He gave out a hint of using recursion. Every time I heard that phrase my brain starts hurting. So, I went blank and gave up on the question.

After the interview, I restudied the problem. I found quite a number of them resort to recursion. While the other recommends the use of Heap's method. But the one that I can easily understand is the insertion method. So, I rewrite the insertion method code in TypeScript:

function permute(entries: number[]): number[][] {
  if (entries.length === 0) return [];
  let output = [[entries[0]]];
  for (let i = 1; i < entries.length; i++) {
    const outputNew = [];
    for (let j = 0; j < output.length; j++) {
      const branch = output[j];
      for (let k = 0; k <= branch.length; k++) {
        const inserted = branch.toSpliced(k, 0, entries[i]);
        outputNew.push(inserted);
      }
    }
    output = outputNew;
  }
  return output;
}

Let me explain how the function work. The first 2 lines of the function are to setup corner case and the initial branch.

// Handling corner case when entries an empty array
if (entries.length === 0) return [];

// While the final output will be returned
// Here, we set it as the initial branch
let output = [[entries[0]]];

The outer loop is to iterate through the rest of the entries one by one.

// We started the insertion from the 1th of entries
for (let i = 1; i < entries.length; i++) {
  // The outputNew will later replace the output
  const outputNew = [];

  // MORE CODE HERE

  // Replace output with the outputNew
  output = outputNew;
}

The inner loops is where the insertion happens.

// We iterate every existing branch that exist in the output.
// It starts with just one branch.
// But the branches will grow as factorial.
for (let j = 0; j < output.length; j++) {
  const branch = output[j];

  // We insert the ith entry at every possible indices.
  // The start (0th) and end (branch.length)
  // index of the branch are included.
  for (let k = 0; k <= branch.length; k++) {
    const inserted = branch.toSpliced(k, 0, entries[i]);

    // Every insertion will be added as a new branch to the output
    outputNew.push(inserted);
  }
}

Supposed that we added the following loggers and call the function:

for (let j = 0; j < output.length; j++) {
  const branch = output[j];
  for (let k = 0; k <= branch.length; k++) {
    console.log(
      `branch: ${JSON.stringify(branch)}, insert: ${entries[i]}, index: ${k}`
    );
    const inserted = branch.toSpliced(k, 0, entries[i]);
    console.log(`inserted: ${JSON.stringify(inserted)}`);
    outputNew.push(inserted);
  }
}
console.log(`new output: ${JSON.stringify(outputNew)}`);
output = outputNew;
...
permute([2, 5, 8]);

We will get the following output:

branch: [2], insert: 5, index: 0
inserted: [5,2]
branch: [2], insert: 5, index: 1
inserted: [2,5]
output: [[5,2],[2,5]]
branch: [5,2], insert: 8, index: 0
inserted: [8,5,2]
branch: [5,2], insert: 8, index: 1
inserted: [5,8,2]
branch: [5,2], insert: 8, index: 2
inserted: [5,2,8]
branch: [2,5], insert: 8, index: 0
inserted: [8,2,5]
branch: [2,5], insert: 8, index: 1
inserted: [2,8,5]
branch: [2,5], insert: 8, index: 2
inserted: [2,5,8]
output: [[8,5,2],[5,8,2],[5,2,8],[8,2,5],[2,8,5],[2,5,8]]

As you can see from the log, the current entry interation will get inserted to existing branch(es) in every possible index, including the start and the end of the branch. This process create more branches in the output. Then, we will repeat the iteration on the next entry - hence creating even more branches.

The permutation is now done. We just need to sort them out with a looping compareFn:

function permuteSorted(entries: number[]): number[][] {
  return permute(entries).toSorted((a, b) => {
    for (let i = 0; i < a.length; i++) {
      if (a[i] === b[i]) {
        continue;
      }
      return a[i] - b[i];
    }
  });
}

Logging the answer to the problem and larger cases:

console.log(`${JSON.stringify(permuteSorted([2, 5, 8]))}`);
// [[2,5,8],[2,8,5],[5,2,8],[5,8,2],[8,2,5],[8,5,2]]
console.log(`${JSON.stringify(permuteSorted([3, 7, 9, 10]))}`);
// [
//  [3,7,9,10],[3,7,10,9],[3,9,7,10],[3,9,10,7],[3,10,7,9],[3,10,9,7],
//  [7,3,9,10],[7,3,10,9],[7,9,3,10],[7,9,10,3],[7,10,3,9],[7,10,9,3],
//  [9,3,7,10],[9,3,10,7],[9,7,3,10],[9,7,10,3],[9,10,3,7],[9,10,7,3],
//  [10,3,7,9],[10,3,9,7],[10,7,3,9],[10,7,9,3],[10,9,3,7],[10,9,7,3]
// ]

Glad that we have done it without recursion. Remember, recursion is never the solution. Always say no to recursion.