Permutation and Mathematical Induction

Last post, I show how basic mathematical induction works. Now, I am going to use it to prove that an algorithm is work correct. In this case, we are going to prove a permutation algorithm, which take an array of unique numbers L, and return an an array of all permutations of L. Let call it perms(L). For example:

1. If L = [ ], then perms(L) would be [ [ ] ].
2. If L = [1, 2, 3], the result of perms(L) will be an array [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Note: the arrary could be any order.

The algorithm that I am going to prove is shown here:

 1: def perms(L)
 2:   return [[]] if L.size == 0
 3:   result = []
 4:   L.each do |elm|
 5:     L1 = L - [elm]
 6:     perms(L1).each |p|
 7:       p1 = [elm] + p
 8:       result << p1
 9:     end
10:   end
11:   return result
12: end

The exact statement that I want to prove to you is: for any given array L of size n, the perms(L) is an array of all size-n permutation of L.

First, basis step: Let L = [ ]. The L.size will be 0. Then the perms(L) will return immediately with value [ [ ] ], which is the array of all size-0 permutation of L.

Inductive step: Let assume statement is true for any array with size n. We have to show that for any array L of size n+1, perms(L) will return an array of all size-(n+1) permutation of L.



Since L have size n+1, the perms won't return immediately and the result is set to an empty array [ ].

In the loop start at line 4: we create an array L1 for each element elm of L by subtract [elm] from L. The new array L1 have size n, and contain all other element of L, except the elm. By assumption, perms(L1) is an array contain all size-n permutation of L1.

Then for an element elm, the loop start at line 6: create all possible size n+1 permutation of L that start with element elm, and also add them to the result array. Since outer loop (line 4:) goes thought all possible element of L, then the result after the loop would contain all possible size n+1 permutation of L. \(#\)

Some may argue that this is not really mathematical induction, it's more like induction reasoning. I say, the important is the basic principal is the same, prove basis case, then show the induction step. Moreover, if you look at the induction proof in graph theory books, or algorithm books, you probably see some thing similar to this.

Hopefully you find this post is interesting and help you to understand more proof that using mathematical induction. Some time it's doesn't clearly stage which part is basis step, which part is induction step, but it's all there, otherwise the proof is not complete.