The Reversal Game
For this assignment you are to write and test a number of functions to solve a puzzle. As usual, your program will be marked by compiling it using g++ on Linux; therefore you should test your program with this compiler and in the Linux OS before submitting it. If you fail to do this, and if your program does not compile it will not be marked.
The Game
The reversal game is a game played with permutations of the integers from 1 to n. A permutation is a set of numbers arranged in a particular order. For example, the possible permutations of the integers from 1 to 3 are: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} and {3,2,1}. Notice that there are n! = 3! = 3*2*1 = 6 such permutations. Also note that values in sets are unique - that is, a set cannot contain duplicates. So {2,1,2} is not a set (it is actually referred to as a bag).
In the reversal game you start with any permutation of the integers 1 to n you like. Here, for example, is one permutation where n = 5:
3 4 5 1 2 is one permutation of the integers from 1 to 5
Playing the game consists of repeatedly reversing the order of the first m digits, where m is always the first number of the permutation. The game stops when the first number of the permutation is 1. The goal is to do as many reversals as possible.
In the permutation given above, m, the first number, is 3, so you reverse the first 3 numbers of the permutation:
3 4 5 1 2 - the first number is 3 so reverse the first three numbers (3 4 5 becomes 5 4 3)
5 4 3 1 2
Now the first number is a 5, and so you reverse the first 5 numbers (i.e. all of them):
5 4 3 1 2 - reverse the first five numbers
2 1 3 4 5
Objective
To play the reversal game you reverse the first m elements of the permutation, where m is the first element of the permutation. The game ends when m equals 1.
The goal of the reversal game is to maximize the score for a particular value of n, in other words to find a permutation of 1, 2, 3, ..., n that needs the greatest number of reversals to get 1 to the start of the permutation.
For even relatively small values of n this is a hard problem to solve since there are n! = 1 * 2 * ... * n different permutations of 1 to n, and there is no obvious pattern to how high-scoring permutations are distributed. And recall that factorials get large very quickly; 5! = 120, 10! = 3,628,800 and 15! = 1,307,674,368,000.
1 - Check Permutation
Write a function that checks to see if its integer array parameter is a permutation, i.e. that it contains all the integers from 1 to n in any order. The function has parameters for the permutation (and integer array) and n (the size of the array)
You should perform enough tests that you are confident isPermutation works correctly in all cases.
2 - Create Permutation
Write a function that generates and returns a permutation where the values are in ascending order. The permutation should be created in a dynamic array, and the function should have a single integer parameter that specifies the permutation's size.
3 - Permutation Score
Write a function that computes and returns the score for a permutation, i.e. the number of reversals required to make the first element of the array equal to 1.
You should perform enough tests that you are confident score works correctly in all cases.
Freeing Dynamic Memory
It's often tricky to determine when to free dynamic memory. Essentially you need to free it when it is no longer required (but not before) and also before you lose the opportunity to free it. Let's look at a concrete example - the score function. Assume that you make a copy as I suggested, then score might look something like this (written in pseudo-code, not C++).
int score(arr)
result = 0
perm = copy(arr) //where perm is an int* to an array in dynamic memory
while not done //i.e. while perm[0] != 1
reverse(perm)
increment result
delete[] perm
return result
Note that you can't de-allocate the memory allocated to perm until you've finished using it, so this can't be done in the loop that is passing perm to the reverse function. On the other hand the memory can't be de-allocated outside the score function since there is no way of accessing the pointer outside the function, and, in any case, it isn't needed at that point. Thus the appropriate time to call delete[] is just before returning from score.
4 - Permutation Print
Write a function that prints a permutation and its score and then a newline (endl) character.
5 - Brute Force
Write a function that uses "brute force" to find and return the permutation with the highest score for small values of n. The function should find the permutation with the highest score by testing every possible permutation of that size.
6 - Brute Force Test
Write a second function called bruteForceTest that uses the bruteForce function to find and then print the highest scoring permutations for values of n from 2 to 11.
7 - High Scoring Permutations
Create and implement your own algorithm for finding high-scoring permutations. To show that it works, have your program create the following output file.
8 - Scoring Output File
Your output file will be scored by comparing it to a set of permutations that the marker has created. Each of your permutations will be scored as follows:
§ 0 if your permutation's score is lower than the marker's permutation score
§ 1 if your permutation's score is greater than, or equal to, the marker's permutation score
Attachment:- Game.rar