Oct 2017

Permutations and combinations are a popular class of computer science problems usually solved (and taught) with recursion - but I think recursion is an unnatural starting point for learning permutations/combinations for people who spend most of their time writing loops. You might see an existing recursive solution and start thinking about what the code is doing on the 2nd call, then notice that 2nd call branches off to several more calls and suddenly you've lost track of the original call or how the results join together. Books/videos/teachers will tell you not to try and trace the algorithm and just trust it instead - but if you can't convince yourself of what it's doing then you may never feel comfortable trusting it.

The typical guidance for finding a recursive solution is to "solve the base case and build", i.e. break the problem into smaller chunks (subproblems) and solve for n=1, then n=2, then n=3 and by then everything should "just work" but if this isn't intuitive, then you may not feel comfortable "trusting it". It's probably because you don't have a mental model for what happens when you start recursing. You can improve your mental model by visualizing various DFS or BFS through a tree or the equivalent algorithm as a series of nested for loops - so here are the iterative solutions to a few combinatorics problems, in Ruby, to help jumpstart a mental model. Note, when using nested for loops, our solution is limited (read: *hard coded*) in what inputs it can take as opposed to a recursive solution which is limited by the size of the call stack.

%W(a b c d).repeated_permutation(4).to_a

This is the simplest, mere nested for loops... but **very slow**: o(n^{n}) - exponential

Note the existence of 4 nested loops means this is hardcoded for an array of size 4

# n**n # 4 nested loops for array of size 4 def repeated_permutation(arr = %W(a b c d)) res = [] arr.each do |c1| arr.each do |c2| arr.each do |c3| arr.each do |c4| res << [c1, c2, c3, c4] end end end end res end # don't pass any args since this nested loop solution # is hardcoded for input of size 4 repeated_permutation()

def repeated_permutation(arr, depth=0) return [[]] if depth == arr.size res = [] arr.each do |c| res.concat repeated_permutation(arr, depth+1).map{|p|p.unshift c} end res end repeated_permutation(%W(a b c d))

%W(a b c d).permutation.to_a

This is the same as the repeated permutation except we reduce the size of the array on each nest/recurse - once we've used a character from the set, we cannot use it on any nested loops/recurses below. Still **very slow** o(n!), but slightly faster than repeated permutations.

Note the existence of 4 nested loops means this is hardcoded for an array of size 4

# n! (4 nested loops for array of size 4) def permutation(arr = %W(a b c d)) res = [] # returns new array without element at index i without = -> (a, i) { a[0...i] + a[(i+1)..-1] } arr.size.times do |i| c1 = arr[i] c2_arr = without.call(arr, i) c2_arr.size.times do |j| c2 = c2_arr[j] c3_arr = without.call(c2_arr, j) c3_arr.size.times do |k| c3 = c3_arr[k] c4_arr = without.call(c3_arr, k) c4_arr.size.times do |l| c4 = c4_arr[l] res << [c1, c2, c3, c4] end end end end res end # don't pass any args since this nested loop solution # is hardcoded for input of size 4 permutation()

Note: I'm slicing the array multiple times in this example for readability: arr[1..-1] which adds o(n) time on each slice operation where n is the size of the new array - but the same code could be rewritten by tracking indices and swapping instead.

def permutation(arr) return [[]] if arr.empty? # returns new array without element at index i without = -> (a, i) { a[0...i] + a[(i+1)..-1] } res = [] arr.each_with_index do |c, i| res.concat permutation(without.call(arr,i)).map{|perm| perm.unshift c} end res end # can pass any array permutation(%W(a b c d))

%W(a b c d e).combination(3).to_a

nest or recurse k times where each of those levels loops over a set of elements of size n-k and on shifts that set of elements to the right for the next level

d eab c

aebc d

a bc d e

abc, abd, abe

d eab c

abecd

a b cd e

acd, ace

d eab c

ab ced

a b c de

ade

ad ebc

a becd

a b cd e

bcd, bce

ad ebc

a bced

a b c de

bde

a bd ec

a b ced

a b c de

cde

Note: the existence of only 2 nested loops means this is hardcoded for k = 2 (so this code can only support k of 2, but arr can be any size)

# 2 nested loops for k of 2 # time complexity is n choose k (number of combinations) # n choose k = n!/(k!*(n-k)!), so between n log n and n^2 def combination(arr = %W(a b c d e), k = 2) res = [] # stop at -2 (2nd from last) because the nested loop covers that # if k was 3, then we'd stop at -3 and have 3 total loops arr[0..-2].each_with_index do |c1, i1| arr[(i1+1)..-1].each do |c2| res << [c1, c2] end end res end # don't pass any args since they have to be hardcoded combination()

Note: I'm slicing the array in this example for readability: arr[1..-1] which adds o(n) time to each iteration where n is the size of the new array - but the same code could be rewritten by tracking indices instead.

def combination(arr, k) return [[]] if k == 0 res = [] arr[0..(0-k)].each_with_index do |c, i| res.concat combination(arr[(i+1)..-1], k-1).map{|combo| combo.unshift(c)} end res end combination(arr=%W(a b c d e), k=3)

These are popular problems where order doesn't matter (combination as opposed to permutation) and you're optimizing for a single value (dollar amount), or multiple values (dollar amount and weight)

- knapsack unbounded: given a set of
**item types**where each item has a weight and value, find the combination of those types (with any amount of repetition) that has the maximum value - knapsack 0/1: given a set of
**items**where each item has a weight and value, find the combination of those that has the maximum value - change-making: given a set of coins, find all combinations (with repetitions) that add up to some amount.

The **brute force recursion solution** for these are simple variations on the combination algo where the base case is changed to ensure you haven't exceeded a dollar amount or weight value - but the **optimum solution involves dynamic programming** (avoidance of solving the same problem over and over again) by caching/memoizing subproblems.