After small changes this program was submitted successfully.
The main bug was that you used lexicografical comparison in next function instead
of alphabetic one (function lessthan).
Also, youd better care about possible spaces in the input, nobody said that word starts
from the line beginning.
IMHO, its better to use standard STL functions for such simple tasks
You could have written 3 times shorter program just calling
sort(v.begin(), v.end(), lessthan)
and
next_permutation(v.begin(), v.end(), lessthan)
Enjoy
Code: Select all
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
using namespace std;
string next(string, int);
bool lessthan(char, char);
string mysort(string s, int len);
int main()
{
int numcases;
cin >> numcases;
string s;
getline(cin, s);
for(int i=0; i<numcases; i++)
{
getline(cin, s);
while (s[0] == ' ') s.erase(0, 1);
while (s[s.length()-1] == ' ') s.erase(s.length()-1, 1);
int len = s.length();
s = mysort(s, len);
while(true)
{
cout << s << "\n";
s = next(s,len);
if(s == "")
break;
}
}
return 0;
}
string next(string in, int len)
{
string result="";
char m,n;
int pos1=-1, pos2=-1;
for(int j=len-1; j>=1; j--)
{
n = in[j];
for(int i=j-1; i>=0; i--)
{
m = in[i];
if(lessthan(m, n) && i > pos1)
{
pos1 = i;
pos2 = j;
}
}
}
if(pos1 != -1)
{
char temp = in[pos1];
in[pos1] = in[pos2];
in[pos2] = temp;
result+=in.substr(0, pos1+1);
char temp2[len - pos1 - 1];
for(int k=pos1+1; k<len; k++)
temp2[k-pos1-1] = in[k];
sort(temp2, temp2+len-pos1-1, lessthan);
for(int k=0; k<len-pos1-1; k++)
result+=temp2[k];
}
return result;
}
inline bool lessthan(char a, char b)
{
char a2 = tolower(a);
char b2 = tolower(b);
if(a2 < b2)
return true;
else if(b2 < a2)
return false;
else return (a < b);
}
string mysort(string s, int len)
{
char arr[len];
for(int k=0; k<len; k++)
arr[k] = s[k];
for(int m=0; m<len-1; m++)
{
for(int n=m+1; n<len; n++)
{
if(lessthan(arr[n], arr[m]))
{
char tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
}
}
string result="";
for(int z=0; z<len; z++)
result+=arr[z];
return result;
}
The point is that given the string, you should be able to generate immediately without computation.. in other words, your algorithm is wrong.