Can anybody give me a hint how to start with the problem below? (It's copied from exercise 3 in the link: https://wiki.ittc.ku.edu/ittc/EECS168:Lab14)
I thought of generating the permutations and checking them whether they can be obtained by swapping 2 adjacent positions and then linking and counting them, but it all seems really complicated. The programming language I'm using is C++. Any ideas will certainly be of great help. Thanks!
Rearranging cartons
Your school has ordered some equipment that has been delivered in a number of very heavy cartons. Each carton has a serial number and the cartons are all lined up in a row. Unfortunately, your teacher asked for the cartons to be placed in a particular sequence and you forgot to tell the people who unloaded the cartons about this. You now have to quickly restore the cartons to the correct order before the teacher comes and sees how you have messed up her instructions. Since the cartons are very heavy, you cannot carry them over long distances. In each step, all you can do is to exchange the position of two adjacent cartons. For instance, suppose the serial numbers on the cartons in the order in which they are unloaded are 34, 29, 12, 78 and 90 and the order in which the cartons were supposed to be arranged is 90, 29, 78, 34, 12. These cartons can be rearranged in the desired order with a minimum of 7 or higher exchanges, as follows:
• Exchange 78, 90 — 34, 29, 12, 90, 78 • Exchange 12, 90 — 34, 29, 90, 12, 78 • Exchange 34, 29 — 29, 34, 90, 12, 78 • Exchange 12, 78 — 29, 34, 90, 78, 12 • Exchange 34, 90 — 29, 90, 34, 78, 12 • Exchange 29, 90 — 90, 29, 34, 78, 12 • Exchange 34, 78 — 90, 29, 78, 34, 12In this example, it can be shown that a mimimum of 7 exchanges are needed to reorder the cartons as desired. You need to rearrange them and report the number of swap (not necessarily the minimum) you needed with the adjacent carton in order to achieve the desired order.
Input format: The first line of input is a single integer N, the total number of cartons. The second line consists of N distinct positive integers, separated by spaces, denoting the serial numbers of the N cartons in the order in which they were unloaded. The third line is another sequence of N integers, denoting the desired order in which the N cartons should be rearranged. The sequence of numbers in the third line is guaranteed to be a permutation of the sequence in the second line.
Output format: The output should be a single integer, the number of exchanges required to achieve the desired sequence of cartons. Here is the sample input and output corresponding to the example discussed above.
Sample input: 5 34 29 12 78 90 90 29 78 34 12 Sample output: 7Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission.
