Question

Problem 3 - use the following definition of permutation below:

List A is a permutation of list B if any of the following are true:

- list A and list B are both null, otherwise

- a.head=b.head, and a.tail is a permutation of b.tail

- a.head≠b.head, and there exists a list C such that

- a.tail is a permutation of b.head:c, and

- b.tail is a permutation of a.head:c

a) Use induction to prove that any finite list is a permutation of itself-in other words, that the permutation relation is reflexive.

b) Using the recursive definition of permutation above, use induction to prove that if list a is a permutation of list b, then list b is a permutation of list a-in other words, that the permutation relation is symmetric.

Answer 1

Defintion of permutation of list : List a is a permutation of list b if any of the following are true: CASE 1) both lists are null, CASE 2) a.head = b.head, and a.tail is a permutation of b.tail, CASE 3) a.head ≠ b.head and there exists another list.

down vote

Your base case is when the list is null. Assume that the property holds for a list of length nn, and look at lists of length n+1n+1. Now we can split the list into head and tail. The tail is a list of length nn. Apply the above definitions, but keep in mind that a=ba=b.