You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 10 Mar '12, 23:54

anmolsood's gravatar image

0★anmolsood
6114
accept rate: 0%

edited 12 Mar '12, 13:19

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.

(12 Mar '12, 06:46) balajiganapath ♦♦6★

Why don't you like stl next_permutation function?

(12 Mar '12, 18:01) iscsi6★

how did u infer he did not like next_permutation function?

(12 Mar '12, 22:30) mkagenius4★

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.

link

answered 12 Mar '12, 02:50

gultus's gravatar image

4★gultus ♦
1.5k11325
accept rate: 51%

edited 12 Mar '12, 02:59

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 :(

(12 Mar '12, 12:42) anmolsood0★

@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.

(12 Mar '12, 20:22) gultus ♦4★

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

(12 Mar '12, 22:27) anmolsood0★

@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.)

(12 Mar '12, 22:33) mkagenius4★

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.)

link

answered 11 Mar '12, 20:07

mkagenius's gravatar image

4★mkagenius
30349
accept rate: 25%

1

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.

(11 Mar '12, 20:59) anmolsood0★

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 ?

(12 Mar '12, 01:16) mkagenius4★
2

@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.

(12 Mar '12, 02:52) gultus ♦4★

@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.

(12 Mar '12, 12:37) anmolsood0★

@gultus , u rock! m/

(12 Mar '12, 22:27) mkagenius4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,901
×591

question asked: 10 Mar '12, 23:54

question was seen: 11,218 times

last updated: 06 Feb '17, 14:06