Problem description

Given a collection of distinct integers, return all possible permutations.

1
2
3
4
5
6
7
8
9
10
11
12
Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Solution: insert-into-all-positions

Consider we have compute the permutations, denoted by set SS for integers with length n - 1. Each element sSs \in S is a string:
e1e2...eke_1e_2...e_k. Now we compute the permutation for adding a new element. The inserting positions (underscore) are shown as follows:
_e1_e2_..._ek_\_e_1\_e_2\_...\_e_k\_. Thus, we implement it as a recursive function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<vector<int> > permute(vector<int>& nums) {
if(nums.empty())
return vector < vector<int> > (1, vector<int>());
vector< vector<int> > res;
int first = nums[0];
nums.erase(nums.begin()); //
vector <vector<int> > words = permute(nums); // n-1
for(auto &a : words) {
for(int i = 0; i <= a.size(); i++){
a.insert(a.begin() + i, first);
res.push_back(a);
a.erase(a.begin() + i);
}
}
return res;
}
};

In OCaml

We implement the question in OCaml.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let insert x lst 
: 'a list list
=
let rec aux prev acc = function
| [] -> List.rev (prev :: [x] :: acc)
| hd :: tl as l ->
aux (prev @ [hd]) (prev :: [x] :: l :: acc) tl
in
aux [] [] lst

let rec permutations = function
| [] -> []
| x :: [] -> [[x]]
| x :: xs ->
List.fold_left (fun acc p -> acc @ insert x p ) [] (permutations xs)