### Thread: How to create a int recursive permutation.

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2009
Posts
5
Rep Power
0

#### How to create a int recursive permutation.

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. "
2. swap needs to work with pointers.

Didn't bother to look at the rest of your algorithm.

• jwdonahue agrees : Swap is definitely broken.
3. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
In the first block of code, nextPermutation() violates seperation of concerns and the one responsibility rules. It prints data and implements an algorithm. Try not to mix those. Functions should do one thing and one thing only. Maybe that one thing is "print a bunch of data", but it should never be "print a bunch data AND do this other thing that has nothing do do with printing". So your original code (the second code block) is actually superior in this regard. Go back to it and fix swap(). Then we'll see whether you have other issues in there.
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2009
Posts
5
Rep Power
0
Alright so now i have this:
(Hope the swap is fixed :D)

Code:
```void 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: ", i);
return(i);
}

int nextPermutation(int array[], int arraySize){
int i;
int max = 10;
int n = max_array(array, arraySize);
if (arraySize == max-1){
for(i=0;i<n;i++)
{
printf("%d",array[i]);
}
printf("\n");
}

for(i=0;i<max;i++)
{
if(array[i]==0)
{
swap(&array[i], &array[arraySize]);
nextPermutation(array, arraySize+1);
swap(&array[i], &array[arraySize]);
}
}

}

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]);
}

}```

Someone has suggested to this as some help ::

Code:
```int ct=-1,n=10,temp[10]={0,0,0,0,0,0,0,0,0,0};
int intArray[10]={1,2,3,4,5,6,7,8,9,10};

permute(int k)
{
int i;
temp[k]=++ct;
if(ct==n-1)
{
for(i=0;i<n;i++)
{
printf("%d",intArray[temp[i]]);
}
printf("\n");
}
for(i=0;i<n;i++)
{
if(temp[i]==0)
{
permute(i);
}
}
ct--;
temp[k]=0;
}

int main()
{
permute(0);
}```
But doesnt help too much since i require the Permute function to take 2 inputs and i think only use 1 array and such so i'm not exactly sure what to change.
5. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Originally Posted by Chackonman
Alright so now i have this:
(Hope the swap is fixed :D)
You hope it's fixed? What happens when you run the program?
6. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2009
Posts
5
Rep Power
0
Well from the current code I don't think it does nothing but can't check atm out of house.

But yeah I noticed no real changes due to the full program being incomplete