1. (implementation + written) It is well known that for any… 1. (implementation + written) It is well known that for any instance of the stable matching problem, a stable matching exists, and the Gale-Shapley algorithm returns one such matching. However, the Gale-Shapley algorithm does not provide much insight into the other stable matchings which may exist. In this question, we aim to find the set of all stable matchings. A natural approach would be to (i) enumerate all possible matchings, and then (ii) check the stability of each matching. Part (a), (b) and (c) below are designed to achieve this task in consecutive steps.(a) (20 pts, implementation + written) Consider an instance with n men and n women. Observe that fixing the order of men as [1, 2, 3,…..n], matching can be defined by the order of the women. For instance, if we have three men whose order is fixed to [1,2,3] and we order three women as [2,3,1], we will be describing the matching {(man1,woman2), (man2, woman3), (man3,woman1)}. Therefore, we can find all possible matchings between men and women by simply fixing the order of men as [1,2, ……n] and finding all possible orderings of women.The pseudocode below provides a function that can be used to enumerate all possible ordering of women. For instance, executing Orders(All, [1, 2, 3], [ ]) for an empty array All = [] would yield All = [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ] function Orders (Array , Start, End) : # similar to Python syntax if Start is empty: Add End to Array else: n =length of Start for i = 0, 1, .. . , n-1: 7 NextEnd = End + Start [1:i+1] #add element at index i to End NextStart =Start[:i] + Start [i+1:] #remove element at index i from Start Orders (Array, NextStart, NextEnd)… Show moreWrite a Python script for the Orders algorithm, provided as in the pseudocode. Your python file should only contain the Orders(Array, Start, End) function. Name your file according to the exam instructions. Also, answer the following questions as a written response:(i) What type of a function is Orders?(ii) What is the big-O complexity of the Orders algorithm.(iii) How many matchings exist when n = 4, n = 8, and n = 16 (provide the answers in your written response)?Computer ScienceEngineering & TechnologyPython Programming DST DS8001
