Give a recursive algorithm to compute a list of all permutationsof a given set S. (That is, compute a list of all possibleorderings of the elements of S. For example, permutations({1, 2,3}) should return {〈1, 2, 3〉, 〈1, 3, 2〉, 〈2, 1, 3〉, 〈2, 3, 1〉, 〈3,1, 2〉, 〈3, 2, 1〉}, in some order.)
Prove your algorithm correct by induction.
