OJ Board

next_permutation returns false when the current stan of container(string) is descending sorted
try to do this: and it's all

Hey,
I use stl next_permutation and get answer.I think there are no scope to show wrong answer but it showed.Whats the problem.Please help me.
Ripon

I've tried to solve this problem not once. I've got WA for this problem again. I just can't understand where I made a mistake. Someone, help me, please!


// 146 ID Codes
#include <iostream.h>
#include <string.h>
//using namespace std;
bool is_last(char* s)
{
int i;
for (i = 0; i < strlen(s) - 1; i++)
if (s < s[i + 1])
return 0;
return 1;
}
void main ()
{
int i, j, k, n;
char id_code[50], *mirror;
cin >> id_code;
while (id_code[0] != '#')
{
if(is_last(id_code))
cout << "No Successor"<< endl;
else
{
int n = strlen(id_code);
k = n - 2;
while (id_code[k + 1] <= id_code[k])
k--;
char min = id_code[k + 1];
int m = k + 1;
for (i = k; i < n; i++)
if (id_code > id_code[k] && id_code < min)
{
m = i;
min = id_code;
}
char letter = id_code[k];
id_code[k] = id_code[m];
id_code[m] = letter;

mirror = new char [n - k - 1];
m = 0;
for (i = n - 1; i > k; i--)
{
mirror[m] = id_code;
m++;
}

m = 0;
for (i = k + 1; i < n; i++)
{
id_code = mirror[m];
m++;
}

cout << id_code<< endl;

}
cin >> id_code;

}
}

Hi
There is function called next_permutation() at the STL library algorithm.h
You can use that. It is just a two line program.

Salman

Let me guess...
You are processing data after the #

Dear cytoplasom,
Thanks for ur reply.But I can't understand what u say.Please explain.
Ripon

The entire file will be terminated by a line consisting of a single #.

When you get to the #, stop processing data.

output for:
"abaacb
cbbaa
#
abaacb"
is:
"ababac
No Successor"

cytoplasom,
I understand.Its ok & accepted.Thanks
ripon

[img][img]146 - ID Codes

Anybody can help me? which the problem with my program? I aways get wrong answer . I don't understand.

/* 146 - ID Codes*/

#include <stdio.h>

main()
{char cod[60],menor,aux;
int i,imenor,j,k,ehalfabetico,m,indice,n;

scanf("%s",cod);
while(strcmp(cod,"#")!=0){
ehalfabetico=0;

n=strlen(cod);
imenor=n-1;

for(i=n-1;i>=0;i--){

if(cod>cod[i-1])
ehalfabetico=1;


if((cod<=cod[imenor])&&(cod[i-1]<=cod[imenor]))
imenor=i;

if(cod>cod[i-1]){

for(m=i;m<n;m++)
if(cod[m]>cod[i-1]) {
imenor=m;break;}

for(m=i;m<n;m++)
if(cod[m]>cod[i-1])
if(cod[m]<cod[imenor])
imenor=m;

aux=cod[imenor];
cod[imenor]=cod[i-1];
cod[i-1]=aux;

j=n-1;
while(j>i){
indice=i;
for(k=i;k<=j;k++)
if(cod[k]>cod[indice])
indice=k;

aux=cod[indice];
cod[indice]=cod[j];
cod[j]=aux;
j=j-1; }
break;
}
}
if(ehalfabetico==1) {
printf("%s\n",cod);
}
else {
printf("No Successor\n");
}

scanf("%s",cod);
}

}

Carefully check this.... I think you should figure out what happens when i = 0.... if (cod[0]>cod[-1]) ... :O
This is not what you intended i suppos, so change the loops to for ( i = n-1; i > 0; --i) then it's fine.
PS.
1. Please when positing code... use the CODE TAG and post FORMATTED CODE.
2. Remove your code using EDIT if you've got Accepted.

Thanks!!! I got Accepted!!!
But which test the program can to get Wrong Answer?

Well, Well....
what would you expect if you run a code like if ( a[0] > a[-1]) or something ? Ask yourself as if you were a compiler you might have got a run time error on invalid memory referencing ...
the compiler behaviour is unexpected... that's the point..... so its not important at which case you are getting wrong answer.
cheers

There is function called next_permutation() at the STL library algorithm.h
You can use that. It is just a two line program.

what's the point?

the point is simple, you dont have to write a complex program.
you can just use a function to print the next permutation.

Please, I've made several tests and my code looks ok. Can you post some critical tests for me ?? I'm trying to get AC for some days and I don't know why I'm getting WA.

Thanks,
Juliano