Hey, i need help to finish a problem i have been trying to do for the past couple of days,

what i need to do is create a recursive premutation with this header "int nextPermutation(int array[], int arraySize)"

An example of what it does it this "Below is the sequence of permutations for n = 3, produced by applying

nextPermutation consecutively:

(1 2 3) ; (1 3 2) ; (3 1 2) ; (2 1 3) ; (2 3 1) ; (3 2 1)

So, the nextPermutation applied to (1 , 2, 3) produces (1, 3, 2),

applied to (1 , 3, 2) it produces (3, 1, 2),

applied to (3, 1, 2) it produces (2, 1, 3)"

So the logic of it is

"If a1,...,an is an arbitrary permutation (where a1,...,an are the numbers 1, 2, …, n in a probably different order) then the “next” permutation is produced by the

following procedure:

(i) If the maximal element of the array (which is n) is not the first element of the

array, say n=ai , where i>1 , then to produce the "next" permutation you need to swap ai and ai−1 .

(ii) If the maximal element of the array is in the first position, i.e. n=a1 , then to

produce the “next” permutation to the permutation (a1,...,an), first find the “next” permutation to the (n-1)-element permutation (a2,...,an), and then

append a1 to the end of thus obtained array of (n-1) elements.

I have attempted multiple different ways but i dont have a clue.

For example i currently have ::

(this doesn't work, just keep repeating the same thing over and over)

Code:void swap(int A, int B){ int temp; temp = A; A = B; B = temp; } int nextPermutation(int array[], int arraySize){ int j; if (arraySize == 10) printf("%d\n", array); else { for (j = arraySize; j <= 10; j++) { swap(array[j], array[arraySize]); nextPermutation(array, arraySize+1); swap(array[j], array[arraySize]); //backtrack } } } int main(){ int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5}; nextPermutation(intArray, 0); int i = 0; for(i = 0; i < 10; i++){ printf("%d ",intArray[i]); }

i used to have something like this....

(This is a snippet before i fixed the swap function and the swap call)

Code:swap(int A, int B){ int temp; temp = A; A = B; B = temp; } int max_array(int array[], int arraySize) { int i, max=-32000; for (i=0; i<arraySize; i++) { if (array[i]>max) { max=array[i]; } } printf("%d \n Max array: ", max) return(max); } int nextPermutation(int array[], int arraySize){ int i; n = max_array(array, arraySize); if (int i; n == array[i] && i > 1; i++){ swap(array[i], array[i-1]); } else if(int i; n == array[i]; i++){ } } void main(){ int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5}; nextPermutation(intArray, 10); int i = 0; for(i = 0; i < 10; i++){ printf("%d ",intArray[i]); }

But i keep getting confused and keep changing it because i think its all wrong with that its telling me to do..... Really got a massive headache over this.

Also here is a further description if you guys need it

"The function receives an integer array argument which is a permutation of integers 1, 2,

…, n. If there is the “next permutation” (the meaning is described in the algorithm below)

to the permutation represented by the array, then the function returns 1 (true) and the array

is changed so that it represents the “next” permutation. If there is no “next” permutation,

the function returns 0 (false) and does not change the array.

Now, to list all the permutations of the numbers 1, 2, …, n, you start with the permutation

(1, 2, …, n) and apply the above algorithm (function nextPermutation) to it to produce

the "next" permutation. Then again you apply nextPermutation algorithm to thus produced

permutation to obtain the "next" permutation etc. Proceeding in this way will allow you to

produce all possible n! permutations of the numbers 1, 2, …, n (if you prove this fact

rigorously, by mathematical induction, you will be awarded 2 bonus marks).

Please note that the last permutation produced in this sequence is (n, …, 2, 1). And this is

the only permutation that does not have the "next" permutation to it. "

agrees : Swap is definitely broken.