To find the next permutation

Input format ;
enter N(<1000) enter K(<=10)
the next k lines each contain a permutaion of 1 to n ;

Output format;
K lines each containg the lexicographically next permutation (entered in input)

There seems to be some small error in my code (using Dev C++ )
Please help me to find it out.

    #include <iostream>
    #include <algorithm>


using namespace std;


int main()
{

int ar[1000][10],N,K,x,i,j,k,max,trig,replace=1001;

cin >> N;
cin >> K; 

 for(i=0;i<K;i++)
 {
   for(j=0;j<N;j++)
   {
     cin >> ar[i][j];
   }
                                 
 }//end of outer most for


for(i=0;i<K;i++)
{

replace=1001;
max=-1; //made the change

for(j=N-1;j>=0;j--)
  {
   
   if(ar[i][j]>max)
    {
      max=ar[i][j];//finding a max to whom a minimum can be found
    }
   else
    {
      trig=ar[i][j];
      for(k=j+1;k<N;k++)
         {
            if(ar[i][k]>trig && ar[i][k]<replace) //made the change
            {
            replace=ar[i][k];
            x=k;
            } 
         }
      ar[i][j]=replace;
      ar[i][x]=trig;
      sort (ar[i]+ j+1,ar[i]+N);
      break;
    }//end of else;
   
   }//end of inner for
   
}//end of outer for

      
      
cout << endl;



for(i=0;i<K;i++)
{
  for(j=0;j<N;j++)
  {
   cout << ar[i][j] << " ";
  }
cout << endl;
}     
      


return 0;
} // end of main

the programme seems to be working fine for small values of N , but for large value of N , it displays incorrect output.

Heres an input for which the code doesn’t work.

50 3

50 33 36 47 17 49 31 4 5 48 42 7 46 23 21 44 3 18 6 43 41 39 19 9 26 1 25 34 13 8 14 29 28 22 38 27 40 37 12 11 16 45 10 20 32 24 35 30 2 15

14 7 12 38 35 10 20 3 13 46 50 37 43 45 30 2 42 41 25 39 5 26 48 27 49 21 32 23 28 40 34 15 6 17 36 16 19 33 24 11 29 9 1 44 22 4 8 31 47 18

25 9 14 47 24 10 8 43 40 20 15 22 26 37 36 44 42 30 32 34 38 19 33 5 28 12 31 50 1 7 13 46 41 49 3 39 27 48 18 29 17 16 35 21 11 23 4 6 2 45

And the correct output for the above input is :-

50 33 36 47 17 49 31 4 5 48 42 7 46 23 21 44 3 18 6 43 41 39 19 9 26 1 25 34 13 8 14 29 28 22 38 27 40 37 12 11 16 45 10 20 32 24 35 30 15 2

14 7 12 38 35 10 20 3 13 46 50 37 43 45 30 2 42 41 25 39 5 26 48 27 49 21 32 23 28 40 34 15 6 17 36 16 19 33 24 11 29 9 1 44 22 4 8 47 18 31

25 9 14 47 24 10 8 43 40 20 15 22 26 37 36 44 42 30 32 34 38 19 33 5 28 12 31 50 1 7 13 46 41 49 3 39 27 48 18 29 17 16 35 21 11 23 4 6 45 2

But my code displays incorrect output for the above mentioned test case.

Thanks.

Thanks.

First of all FOR GOD sake indent your code properly.

may be this is the error- if(ar[i][k] > trig && ar[i][k] < replace)

(and yes, also put spaces where needed, like before and after “=” sign. etc.)

1 Like

Sorry about indentation , I am new to programming.

i can’t find error in the line you mentioned. My purpose for that if condition is to find the smallest value which is greater than trig so that it can swapped with trig.

1 Like

Hey dude, where is your concentration?
Notice :my line—> if(ar[i][k] > trig && ar[i][k] < replace) ,
and your line----> if(ar[i][k] > trig && ar[i][j] < replace) ,
can you find the difference ?

I haven’t really studied the program for logic errors. But here are my two cents of advice.

You have stated N<1000 and k<=10 but you seem to have coded for the reverse.

You are setting max=ar[i][N]; but there is no value in ar[i][N] really so it picks up a stray value or results in a segmentation fault. Replace this with max = -1.

Also consider the change suggested by mkagenius. The second condition in ar[i][k]>trig && ar[i][j] < replace as it is now in your code is always true but I doubt if that is the real intended behaviour.

If after considering these changes still if your code is not behaving as expected then let us know but this time it would be better if you can also provide the input for which it is failing.

EDIT: Hope you were writing this code just for learning purpose. In reality you would never need to write a code for lexicographically next permutation. You can simply use next_permutation available in STL.

4 Likes

@mkagenius be little soft on noob mistakes, no point using such harsh words. If people do repeat the mistakes then I can understand the usage of harsh words.

2 Likes

Please accept the answer (By clicking on the tick in the left side of the answer) if you feel it has answered your question. If not then add comments requesting clarification.

@mkagenius && @gultus :- Thanks a lot and Sorry. I made the changes and yet the code is not working perfectly for large values of n(let’s say 50). The code seems to work perfectly fine for small values.

Updated a test case in the question and yes i am writing this code for learning purpose. There still seems to be something wrong with the code :frowning:

Why don’t you like stl next_permutation function?

1 Like

@anmolsood It would obviously not work as expected for the input you have provided since you coded for N<=10 and K<=1000 while you are now inputting N=50. Make the change int ar[10][1000] instead of int ar[1000][10] this will resolve the issue.

@gultus , u rock! \m/

@guitus Thanks . That resolves the issue . I am such a noob.

how did u infer he did not like next_permutation function?

@anmolsood , he is gultus not guitus, see u don’t pay attention to small things. (just kidding as you are in school. All the best for your future.)

april 2017 Printable Calendar
Rajkumar

May 2017 Calendar
may calendar 2017