permutation

[cmp]

Write a function that computes and returns the score for a permutation, i.e. the number of reversals required to make arr[0] == 1.

HAVE TO USE FOLLOWING FORMAT:

// POST: Returns the number of reversals needed to make arr[0] == 1
//       if the reversal game were played on arr
// Note: If arr[0] == 1 initially, then score(arr, n) returns 0

AND this is what i could muster;

int score(int arr[], int n)
{ 
int lo,hi;
for(lo=0,hi=size-1;lo<hi;lo++,hi--){
int temp=arr[lo];
arr[lo]=arr[hi];
arr[hi]=temp;}

return score; 
}

Any help please.
Thank you.

[Click_here]

You need to be clearer on what you are trying to achieve

How many elements are you going to be having as your max input?
I'm guessing that it's a 2D input (?)
Have you read up on permutations? Permutation - Wikipedia, the free encyclopedia
(You don't want to be doing it "the suckers way")
Does only a[0] have to equal one? i.e. Does a[1] have to equal anything?

Would this be an appropriate sequence of events?
2314
2134
1234

[edit]
... Or would this do?
3241
3214
3124
1324

(note the final order)
[/edit]

[cmp]

Write a function that computes and returns the score for a permutation, i.e. the number of reversals required to make arr[0] == 1.

// PRE: is_permutation(arr, n)
// POST: Returns the number of reversals needed to make arr[0] == 1
// if the reversal game were played on arr
// Note: If arr[0] == 1 initially, then score(arr, n) returns 0

int score(int arr[], int n)


You should perform enough tests that you are confident score works correctly in all cases.

Reversals
To compute the score you will have to play the reversal game, which will entail writing a reverse function which reverses the first mvalues in the permutation, where m is the first element of the permutation. Note that I went over a function in class that does this which you are welcome to use as a starting point.

Array Copies
One thing to watch out for is changing your permutation when you don't want to. Let's assume that you are testing a permutation to find its score. The permutation is passed to the score function which will have to perform reversals on it (to find the score), thereby changing the permutation. Remember that an array variable is a pointer, so any changes you make to the permutation in the score function will be reflected outside the function. This can be very undesirable if you are trying to keep track of which permutation has the highest score.

The solution to this is to make a copy of the permutation as soon as it is passed to the score function, and then perform reversals on the copy leaving the original untouched. When you make a copy you will have to create it in dynamic memory, which leads to the next question - when should you free (de-allocate) this dynamic memory. You may well want to write another function that makes a copy of the parameter.

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 as necessary
free(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 free is just before returning from score.



this work?

int score(int arr[], int size){


    score = 0;
	// allocate some temporary space to hold a copy of the array
	int *perm = malloc(size * sizeof(int));
	// make a copy of the array
	for (int i=0; i < size; i++)
	{
		perm[i] = arr[i];
	}
	// reverse the array until the first element is 1
	while(perm[0] != 1)
	{
		reverse(perm);
		score++;
	}
	// now free the temporary space
	free(perm);
	return score;
}