### Where is it going wrong: Next Permutation Logical Error

I wrote this code to solve a problem in which the user inputs a permutation
of size 'N' and the next permutation of the same elements has to be generated.
given 3 2 5 4 1, starting from the right, the first no. has to be searched which
has a no. greater to it on its right. Here it is 2. Now an array is generated
containing all no.s on its right and greater than it. For 2, it is: 5,4.
Out of these the smallest member is searched for and switched with 2. So, 4 is
switched with 2 to get the Next Permutation: 3 4 5 2 1.

The code I wrote does not show any error but does not return the correct value
when run and gives the same value instead. If I enter '3 2 5 4 1' it returns
the same value as the answer.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758`` ``````#include #include void main() { clrscr(); int N,M,i,n,c,swap,flag,count,small,m; int Array[100],Key[100]; cout<<"Enter N: "; cin>>n; cout<<"\n"; for(n=0;n<100;n++) { Array[n]=0; } //Setting all members of array =0 for(n=0;n>Array[n]; } //Entering the permutation M=N; flag=0; while(flag<1) { M=M-1; i=N; c=0; for(n=i;n>M;n=n-1) //Loop which checks the number with greater members on its right { if(Array[M]
Please format your code better, i.e. matching brackets should line up with each other.

Here is a permutate function I wrote before. It works the same as the next_permutate function in the algorithm library:

 ``12345678910111213141516171819202122232425`` ``````bool Lexi_Permute(char* v1) { long S(__Size(v1));//Size of v1 int g, s; bool didPermute = false; for (g = S-2; g >= 0; --g) { if (v1[g] < v1[g+1]) { for (s = S-1; s > g; --s) if (v1[s] > v1[g]) { _swap(v1[s], v1[g]); didPermute = true; break; } for (s = (g+1), g = (S-1); s < g; ++s, --g) _swap(v1[s], v1[g]); break; } } return didPermute; }``````

Some articles you can look at:
http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
http://wordaligned.org/articles/next-permutation
http://www.programiz.com/c-programming/examples/lexicographical-order
http://marknelson.us/2002/03/01/next-permutation/

Your code: (not fixed, just indented)
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465`` ``````#include #include #include void main() { clrscr(); int N, M, i, n, c, swap, flag, count, small, m; int Array[100], Key[100]; cout << "Enter N: "; cin >> N; cout << N; // for (n = 0; n < 100; n++) { // Array[n] = 0; // } //Setting all members of array =0 std::fill(Array, sizeof Array, 0); for (n = 0; n < N; n++) { cin >> Array[n]; } //Entering the permutation M = N; flag = 0; while (flag < 1) { M = M - 1; i = N; c = 0; for (n = i; n > M; n = n - 1) //Loop which checks the number with greater members on its right { if (Array[M] < Array[i]) { Key[c] = Array[i]; //'Key' is the array containing numbers from Array greater than Array[M] and on its right side c = c + 1; flag = flag + 1; } } } count = 0; while (count < 1) { small = 0; for (m = 0; m < c; m++) { if (Key[m] == small) { count = count + 1; swap = Key[m]; } } small = small + 1; } //This while loop assigns 'swap' the value of smallest member of 'Key' with which Array[M] has to be switched to produce the next permutation. for (n = 0; n < N; n++) { if (Array[n] == swap) { m = n; } } //Array[m] is the member with which Array[M] has to be switched with. Array[m] = Array[M]; Array[M] = swap; //Code to swich values. for (n = 0; n < N; n++) { cout << Array[n] << " "; } //Printing the Next Permutation. getch(); }``````
Last edited on
 ``12345678910111213141516171819202122`` ``````#include // correction. int main() // correction { int N,M,i,n,c,swap,flag,count,small,m; // int Array[100],Key[100]; int Array[100] = {0} ; // all elements set to 0. int Key[100] = {0} ; // all elements set to 0. cout<<"Enter N: "; cin>>n; // notice that this is n, not N. cout<<"\n"; // don't need this loop now: // for(n=0;n<100;n++) // { Array[n]=0; } for(n=0;n>Array[n]; // ... }``````

The first thing I noticed, besides the fact that you're using an antiquated compiler is that N's value is indeterminate. It could be anything, but you're using it to limit your for loop.

On line 22 (in the OP) you set i equal to N which (after you make the above correction) would be the number of elements in the array. This is one past the index of the values you read into the array, and since you set all values of array to 0, it is 0.

The value of i never changes during this loop. It is repeatedly set to the same value. It is possible for M to become negative during the loop beginning on line 19, which means it will be an invalid index into Array on line 27.

In short, you've got a whole lot of problems with your code. I didn't bother reading further.