- If L = [ ], then perms(L) would be [ [ ] ].
- 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.
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.
No comments:
Post a Comment