# Permutations

## Question

### Problem Statement

Given a list of numbers, return all possible permutations.

#### Example

For nums = [1,2,3], the permutations are:

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


#### Challenge

Do it without recursion.

## 题解1 - Recursion(using subsets template)

### Python

class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
alist = []
result = [];
if not nums:
return result

self.helper(nums, alist, result)

return result

def helper(self, nums, alist, ret):
if len(alist) == len(nums):
# new object
ret.append([] + alist)
return

for i, item in enumerate(nums):
if item not in alist:
alist.append(item)
self.helper(nums, alist, ret)
alist.pop()


### C++

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
vector<vector<int> > result;
if (nums.empty()) {
return result;
}

vector<int> list;
backTrack(result, list, nums);

return result;
}

private:
void backTrack(vector<vector<int> > &result, vector<int> &list, \
vector<int> &nums) {
if (list.size() == nums.size()) {
result.push_back(list);
return;
}

for (int i = 0; i != nums.size(); ++i) {
// remove the element belongs to list
if (find(list.begin(), list.end(), nums[i]) != list.end()) {
continue;
}
list.push_back(nums[i]);
backTrack(result, list, nums);
list.pop_back();
}
}
};


### Java

public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;

List<Integer> list = new ArrayList<Integer>();
dfs(nums, list, result);

return result;
}

private void dfs(int[] nums, List<Integer> list, List<List<Integer>> result) {
if (list.size() == nums.length) {
result.add(new ArrayList<Integer>(list));
return;
}

for (int i = 0; i < nums.length; i++) {
if (list.contains(nums[i])) continue;
list.add(nums[i]);
dfs(nums, list, result);
list.remove(list.size() - 1);
}
}
}


### 源码分析

list.size() == nums.size()时，已经找到需要的解，及时return避免后面不必要的for循环调用开销。

## 题解2 - Recursion

### Python

class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def permute(self, nums):
if nums is None:
return [[]]
elif len(nums) <= 1:
return [nums]

result = []
for i, item in enumerate(nums):
for p in self.permute(nums[:i] + nums[i + 1:]):
result.append(p + [item])

return result

class Solution2:
# 类似 subset的模版
def permute(self, nums):
if not nums:
return []
res = []
self.helper(sorted(nums), res, [])
return res

def helper(self, nums, res, tmp):
if not nums:
res.append(tmp[:])
return
for i, num in enumerate(nums, 1):
self.helper(nums[:i] + nums[i + 1:], res, tmp + [num])


### C++

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > result;

if (nums.size() == 1) {
result.push_back(nums);
return result;
}

for (int i = 0; i < nums.size(); ++i) {
vector<int> nums_new = nums;
nums_new.erase(nums_new.begin() + i);

vector<vector<int> > res_tmp = permute(nums_new);
for (int j = 0; j < res_tmp.size(); ++j) {
vector<int> temp = res_tmp[j];
temp.push_back(nums[i]);
result.push_back(temp);
}
}

return result;
}
};


### Java

public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> numsList = new ArrayList<Integer>();

if (nums == null) {
return result;
} else {
// convert int[] to List<Integer>
for (int item : nums) numsList.add(item);
}

if (nums.length <= 1) {
result.add(numsList);
return result;
}

for (int i = 0; i < nums.length; i++) {
int[] numsNew = new int[nums.length - 1];
System.arraycopy(nums, 0, numsNew, 0, i);
System.arraycopy(nums, i + 1, numsNew, i, nums.length - i - 1);

List<List<Integer>> resTemp = permute(numsNew);
for (List<Integer> temp : resTemp) {
temp.add(nums[i]);
result.add(temp);
}
}

return result;
}
}


### 源码分析

Python 中使用len()时需要防止None, 递归终止条件为数组中仅剩一个元素或者为空，否则遍历nums数组，取出第i个元素并将其加入至最终结果。nums[:i] + nums[i + 1:]即为去掉第i个元素后的新列表。

Java 中 ArrayList 和 List 的类型转换需要特别注意。

## 题解3 - Iteration

1. 从后往前寻找索引满足 a[k] < a[k + 1], 如果此条件不满足，则说明已遍历到最后一个。
2. 从后往前遍历，找到第一个比a[k]大的数a[l], 即a[k] < a[l].
3. 交换a[k]a[l].
4. 反转k + 1 ~ n之间的元素。

### Python

class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def permute(self, nums):
if nums is None:
return [[]]
elif len(nums) <= 1:
return [nums]

# sort nums first
nums.sort()

result = []
while True:
result.append([] + nums)
# step1: find nums[i] < nums[i + 1], Loop backwards
i = 0
for i in xrange(len(nums) - 2, -1, -1):
if nums[i] < nums[i + 1]:
break
elif i == 0:
return result
# step2: find nums[i] < nums[j], Loop backwards
j = 0
for j in xrange(len(nums) - 1, i, -1):
if nums[i] < nums[j]:
break
# step3: swap betwenn nums[i] and nums[j]
nums[i], nums[j] = nums[j], nums[i]
# step4: reverse between [i + 1, n - 1]
nums[i + 1:len(nums)] = nums[len(nums) - 1:i:-1]

return result


### C++

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > result;
if (nums.empty() || nums.size() <= 1) {
result.push_back(nums);
return result;
}

// sort nums first
sort(nums.begin(), nums.end());
for (;;) {
result.push_back(nums);

// step1: find nums[i] < nums[i + 1]
int i = 0;
for (i = nums.size() - 2; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
break;
} else if (0 == i) {
return result;
}
}

// step2: find nums[i] < nums[j]
int j = 0;
for (j = nums.size() - 1; j > i; --j) {
if (nums[i] < nums[j]) break;
}

// step3: swap betwenn nums[i] and nums[j]
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;

// step4: reverse between [i + 1, n - 1]
reverse(nums, i + 1, nums.size() - 1);
}
return result;
}

private:
void reverse(vector<int>& nums, int start, int end) {
for (int i = start, j = end; i < j; ++i, --j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
};


### Java - Array

class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;

// deep copy(do not change nums)
int[] perm = Arrays.copyOf(nums, nums.length);
// sort first!!!
Arrays.sort(perm);

while (true) {
// step0: add perm into result
List<Integer> tempList = new ArrayList<Integer>();
for (int i : perm) tempList.add(i);
result.add(tempList);

// step1: search the first perm[k] < perm[k+1] backward
int k = -1;
for (int i = perm.length - 2; i >= 0; i--) {
if (perm[i] < perm[i + 1]) {
k = i;
break;
}
}
// if current rank is the largest, exit while loop
if (k == -1) break;

// step2: search the first perm[k] < perm[l] backward
int l = perm.length - 1;
while (l > k && perm[l] <= perm[k]) l--;

// step3: swap perm[k] with perm[l]
int temp = perm[k];
perm[k] = perm[l];
perm[l] = temp;

// step4: reverse between k+1 and perm.length-1;
reverse(perm, k + 1, perm.length - 1);
}

return result;
}

private void reverse(int[] nums, int lb, int ub) {
for (int i = lb, j = ub; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}


### Java - List

class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (nums == null || nums.size() == 0) return result;

// deep copy(do not change nums)
List<Integer> perm = new ArrayList<Integer>(nums);
// sort first!!!
Collections.sort(perm);

while (true) {
// step0: add perm into result
result.add(new ArrayList<Integer>(perm));

// step1: search the first num[k] < num[k+1] backward
int k = -1;
for (int i = perm.size() - 2; i >= 0; i--) {
if (perm.get(i) < perm.get(i + 1)) {
k = i;
break;
}
}
// if current rank is the largest, exit while loop
if (k == -1) break;

// step2: search the first perm[k] < perm[l] backward
int l = perm.size() - 1;
while (l > k && perm.get(l) <= perm.get(k)) l--;

// step3: swap perm[k] with perm[l]
Collections.swap(perm, k, l);

// step4: reverse between k+1 and perm.size()-1;
reverse(perm, k + 1, perm.size() - 1);
}

return result;
}

private void reverse(List<Integer> nums, int lb, int ub) {
for (int i = lb, j = ub; i < j; i++, j--) {
Collections.swap(nums, i, j);
}
}
}


powered by