LeetCode: Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

---

There are two ideas to compute permutations. One is to compute the next permutation based on the current one, which has been talked in the previous problem 'Next Permutation'. And this is also how STL implements the function next_permutation in <algorithm>. The other idea is from online, we can perform a dfs like way to compute each permutation, with which we swap the start element with current element each time.

C++ Code:

/*
 * func: permutation_helper
 * goal: helper function to collect each permutation
 * @param num: original number vector
 * @param start_pos: start position in the list for each permutation
 * @param result: final result set
 * return:
 */
void permutation_helper(vector<int> &num, size_t start_pos, vector<vector<int> > &result) {
    if (start_pos == num.size() - 1) {
        result.push_back(num);
        return;
    }
    for (size_t i = start_pos; i < num.size(); ++i) {
        swap(num[start_pos], num[i]);
        permutation_helper(num, start_pos + 1, result);
        swap(num[start_pos], num[i]);
    }
}

/*
 * func: permutation
 * goal: find all possible permutations for the given vector
 * @param num: the given number vector
 * return: a vector of all possible permutations
 */
vector<vector<int> > permutation(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int> > result;
    permutation_helper(num, 0, result);
    return result;
}

In Python, there is also a library function itertools.permutations that can compute permutations. Here I introduced another implementation found in stackoverflow.

# func: return all possible permutations of the given list
# @param num: given list
# @return: a list of all possible permutations
def permutations(num):
    if len(num) == 0:
        return [[]]
    else:
        return [[x] + remaining for x in num for remaining in permutations(delete(num, x))]

def delete(num, item):
    copy = num[:]
    copy.remove(item)
    return copy

Reference Link:

1.[closed] Permutations - LeetCode: http://discuss.leetcode.com/questions/224/permutations?sort=votes&page=2

2.algorithm - How to generate all permutations of a list in Python - Stack Overflow: http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python