02-15-2018
Heaps algorithm is a simple and elegant solution to finding permutations. Finding permutations is one of the fundamental problems of computing and provides the basis for backtracking problems. However permutation problems are encountered less frequently in real world applications.
HISTORYThis algorithm was first proposed by B. R. Heap in a paper in The Computer Journal in 1963. You can read the paper here.
Heaps algorithm finds all permutations of an array. It first iterates through the array and for each item finds the all possible permutations of length - 1 of the array. The recursive function works like so. It accepts the array and the size of it. It calls itself recursively, with the size of it getting shorter by one each time. When the size equals 1 it prints out the array and returns. Inside the for loop, if the size of the array is odd, a swap between the first and the last or size-1 positions occurs.
The loop continues and another recursive call is made on the new altered array. Again if the size variable is equal to one, the array is printed and the function returns. The loop continues and again, since the size is the same in this loop, in our case it is even, another swap is made.
The reason why this works is intuitively difficult to get. The wikipedia article even had an incorrect version on its page for a long time because it is often memorized and therefore it is easy to make a mistake.
This article provides a good explanation of why this works. Another excellent article generating permutations is here.
Time Complexity:
Space Complexity:
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
size = len(nums)
return self.permuteRec(nums, size, result)
def permuteRec(self, nums, n, result):
if n == 1:
copy = nums[:]
result.append(copy)
return result
for i in range(n):
result = self.permuteRec(nums, n-1, n, result)
if (n % 2 == 1):
nums[0], nums[n-1] = nums[n-1], nums[0]
else:
nums[i], nums[n-1] = nums[n-1], nums[i]
return result