Generating permutations is a classic algorithmic problem, and it’s a great use case for dynamic programming.
As my friend and professional mentor James Powell at Don’t Use This Code describes, the commonalities between all dynamic programming algorithms are:
The “Generate Permutations” Leetcode problem can be solved using dynamic programming, but the first time I tried it, I found it a bit trickier than I’d expected. Following are some notes on it:
(There’s a lively debate on the value of LeetCode, which I will not touch here. Understanding algorithms is valuable. I’ll leave it at that.)
With generating permutations, you can define the problem using the DP characteristics as follows:
Overlapping subproblems: generating permutations of a collection of N objects requires us to generate permutations of collections of N-1 of those objects. To get the collection of N-1 objects, we need to remove one item—hopefully I’ve made that obvious.
A concrete example is generating permutations of the first N cardinal numbers. The permutations of the cardinal numbers from 0 to 3 can be built from the permutations of the cardinal numbers from 0 to 2, which can be built from … you see the pattern.
Optimal substructure: for any collection of objects, in the most general sense of objects, you start with the empty ordered container data type of your choice—list, vector, ArrayList, whatever your favored language uses here. Then begin to construct the final answer by taking each object and adding it to the empty list, one at a time. Using the cardinal numbers, this would give you lists like [0], [1], [2], and onwards. To continue constructing your complete solution, take each of the “answers-in-progress” and one of the remaining numbers. Two more intermediate solutions are generated by adding the second number before and after the element of the singleton list.
(To do: add a visualization)
This gives us all we need to know to write an algorithm for generating permutations, which I’ve sketched out below in Python:
def permutations(xs):
# Recursive, generator-based approach.
# If the list `xs` is empty or has a single element, it has one
# permutation, and that permutation is `xs` itself.
if len(xs) <= 1:
yield xs
return
# Otherwise: we can recurse on the permutations of the sublist
# without xs[0], and for each of those (we know this
# since each call makes a recursive call with a sublist one element
# smaller)
# and for each of those "partial permutations" (calling them
# partial" because they don't have xs[0]), we can get a full
# permutation by yielding the permutation with xs[0] at index i,
# for every valid index i.
for permutation in permutations(xs[1:]):
for i in range(len(xs)):
yield permutation[:i] + xs[0:1] + permutation[i:]
Enjoy!