Permutations in Python

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        if (not nums):
            return []

        N = len(nums)
        if (N == 1):
            return [nums]

        A = nums    # rename

        # There should be N! permutations
        def fac(n):
            if (n < 0):
                return False
            elif (n < 1):
                return 1
            else:
                return n*fac(n-1)

            """
            # Iterative:

            answer = 1
            for i in xrange(1,n+1):
                answer *= i

            return answer
            """

        total = fac(N)
        print("total perms: %i! = %i" % (N, total))

        # Generate all permutations
        perms = []
        for _ in xrange(total):
            # Find pivot
            pivot = None
            for i in xrange(N-2, -1, -1):
                if (A[i] < A[i+1]):
                    pivot = i
                    break

            if pivot is None:
                A.reverse()
                copy = [n for n in A]           # Why is this necessary?
                perms.append(copy)
            else:
                # Find successor in subarray
                successor = pivot+1         # Starting guess
                for j in xrange(pivot+1, N):
                    if (A[j] > A[pivot] and
                        (A[j] - A[pivot] <= A[successor] - A[pivot])):
                            successor = j

                # Swap pivot and successor
                A[pivot], A[successor] = A[successor], A[pivot]

                # Reverse subarray
                A[pivot+1:] = reversed(A[pivot+1:])

                # Add to list
                copy = [n for n in A]               # Why is this necessary?
                perms.append(copy)
        return perms


s = Solution()

# Test cases
a0 = [1,2,3]

y0 = [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]]

print("input: %r" % a0)
print("output: %r" % (s.permute(a0)))