Intuiting the algos behind permutations and combinations

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.

Repeated Permutation

The Ruby stdlib solution

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

narrative

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

iterative

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()

recursive

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))

Non-repeated Permutation

The Ruby stdlib solution

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

narrative

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.

iterative

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()

recursive

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))

Combinations (n choose k)

The Ruby stdlib solution

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

narrative

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

first result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

abc, abd, abe

second result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

acd, ace

third result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

ade

fourth result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

bcd, bce

fifth result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

bde

sixth result set (dives depth of 3 (or k))

a b c d e

a b c d e

a b c d e

cde

iterative

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()

recursive

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)

Variations of the combinations algo: knapsack, change-making (combinatorial optimization)

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.