EXTRA: Brute-Force Permutations

Brute-force permutations are a method of generating all possible arrangements of a given set of elements. This technique generally has a time complexity of O(n!) because, for a set of n elements, there are n! (factorial of n) possible permutations.

Example Code: Brute-Force Permutations

Let's consider a simple example of generating all permutations of a list of numbers:

function getPermutations(arr) {
  let result = [];

  // Base case: if the array has only one element, return it as the only permutation
  if (arr.length === 1) {
    return [arr];
  }

  // Recursive case: for each element, create a permutation with it as the first element
  for (let i = 0; i < arr.length; i++) {
    const firstElement = arr[i];
    const remainingElements = arr.slice(0, i).concat(arr.slice(i + 1)); // Get the rest of the array

    // Recur to generate permutations for the remaining elements
    const remainingPermutations = getPermutations(remainingElements);

    // Prepend the first element to each of the permutations of the remaining elements
    for (let perm of remainingPermutations) {
      result.push([firstElement, ...perm]);
    }
  }

  return result;
}


const numbers = [1, 2, 3];
console.log(getPermutations(numbers));

Example Output:

For the input [1, 2, 3], the output will be:

[
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1]
]