Question 3. (10 points) Recursive permutations For every positive integer n, there are nl permutations of { 1, 2, . . . , n} There is an ordering on the permutations defined by the lexicographic (dictionary) order on lists, e.g. for n -3 we have the following ordering of the permutations 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 (5 points) Give a recursive algorithm which takes two positive integers n and k 1,2, .. , n!), which then returns the kth permutation of {1, 2, , ?} in O(n2). E.g. for n 3, k 4 the algorithm should output 2,3,1 Hint 3.1. Try to find the first number in the permutation, by counting the permutations 2. (5 points) Give a recursive algorithm which takes a permutation of { 1, 2, . . . ,n) and returns the position of the permutation in the lexicographic ordering of all permutations in O(n2) E.g. for the input (3, 1,2), the algorithm should output 5 Hint 3.2. Try to reverse the above procedure to get the position