# Permutation

·

Say we have a set `[1,2,3]`, its permutations are `[ [ 3, 2, 1 ], [ 2, 3, 1 ], [ 2, 1, 3 ], [ 3, 1, 2 ], [ 1, 3, 2 ], [ 1, 2, 3 ] ]`

It's very easy to understand what permutation is, but the problem is how to get them.

Let's take a set `[1,3,5]` as an example, here is the process:

``````[[]] =>
[[1]] =>
[[3,1], [1,3]] =>
[[5,3,1],[3,5,1],[3,1,5], [5,1,3],[1,5,3],[1,3,5]]
``````

We can see clearly that we start with a queue with an empty array element. Loop the queue, and insert new set element into all the positions of the current queue element. For example, if current queue element is `[3,1]`, new set element is 5, then we insert 5 in all positions and then we get `[5,3,1], [3,5,1], [3,1,5]`

Let's use this process to solve the leetcode Permutations problem.

``````function permute(nums: number[]): number[][] {
let q: number[][] = [[]];
for (const num of nums) {
const end = q.length;
for (let i = 0; i < end; i++) {
for (let j = 0; j <= q[i].length; j++) {
const copy = q[i].slice();
copy.splice(j, 0, num);
q.push(copy);
}
}
q = q.slice(end); // note here, discard the previous temporary element
}
return q;
};
``````