Permutations

Problem: Permutations

Permutations can be calculated easily by recurrence implementing backtracking. But let us get back to the definition of permutations, they are all possible permutations of certain numbers. So we can find the all possible permutations by switching all-allowed-to-switch numbers.

Code in Python:

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = [nums]
        for i in xrange(1, len(nums)):
            m = len(ans)
            for k in xrange(m):
                for j in xrange(i):
                    ans.append(ans[k][:])
                    ans[-1][i], ans[-1][j] = ans[-1][j], ans[-1][i]
        return ans
        # res = []
        # if not len(nums):
        #     return
        # for i in xrange(len(nums)):
        #     ans = self.permute(nums[:i]+nums[i+1:])
        #     if ans:
        #         for a in ans:
        #             cur = [nums[i]]
        #             cur.extend(a)
        #             res.append(cur)
        #     else:
        #         res.append([nums[i]])
        # return res

To better explain the code, let's see an example. First, we set original numbers [1,2,3] as one of the solutions. Then we begin to change numbers with the 2nd element by elements before it, thus we get [[1,2,3],[2,1,3]]. Then we begin to change numbers with 3rd element by elements before it on acknowledged solutions, thus we can avoid duplicate changing. And we can get [[1,2,3],[2,1,3],[3,2,1],[1,3,2],[3,1,2],[2,3,1]]. Repeat these steps we can get all possible solutions.

Code in Java:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        perm(result,nums,0,nums.length-1);
        return result;
    }
    public static void perm(List<List<Integer>> result, int[] nums, int start, int end){
        if(start==end){
            Integer[] ele = new Integer[nums.length];   // Don't use primitives
            for(int i=0; i<nums.length; i++){
                ele[i] = nums[i];
            }
            result.add(Arrays.asList(ele));
        }
        else{
            for(int i=start; i<=end; i++){
                // Use swapping to do subarray
                int temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;

                perm(result, nums,start+1,end);

                temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;
            }
        }
    }
}