
Code: Select all
Code removed after AC
Moderator: Board moderators
Code: Select all
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cctype>
#include <set>
using namespace std;
//#define DEBUG
//#undef DEBUG //uncomment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#else
#define debug(a, end)
#endif
typedef pair<int, int> point;
typedef long long int64; //for clarity
typedef vector<int> vi; //?
typedef vector<point> vp; //?
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //change max
#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)
/*global variables*/
struct compare
{
bool operator() (const string& a, const string& b)
{
bool t = false;
for (size_t i = 0; i < a.length() && i < b.length(); ++i)
if (toupper(a[i]) < toupper(b[i]))
return true;
else if (toupper(a[i]) > toupper(b[i]))
return false;
else if (toupper(a[i]) == toupper(b[i]))
if ( a[i] < b[i] )
return true;
/*t = a[i] < b[i] ? true : false;
return t;*/
}
};
struct comp
{
bool operator() (const char& a, const char& b)
{
debug(a, TAB); debug(b, TAB); debug((isupper(a) ? a < b : b > a), endl);
return (isupper(a) ? a < b : b > a);
}
};
string word;
/*global variables*/
void dump()
{
//dump data
}
bool getInput()
{
//get input
cin >> word;
return true;
}
void process()
{
//process input
set<string, compare> words;
//SORT(word);
do
{
words.insert(word);
debug(word, endl);
}
while (next_permutation(word.begin(), word.end(), comp()));
//quick hack.
do
{
words.insert(word);
debug(word, endl);
}
while (next_permutation(word.begin(), word.end()));
//sort(words.begin(), words.end(), compare());
//SORT(words);
for (set<string>::iterator it = words.begin(); it != words.end(); ++it)
printf("%s\n", it->c_str());
debug(words.size(), endl);
}
int main()
{
int nc;
scanf("%d", &nc);
while (nc-- > 0)
{
getInput();
process();
/*CLEAR GLOBAL VARIABLES!*/
/*CLEAR GLOBAL VARIABLES!*/
}
return 0;
}
mgavin2 wrote:WA ... I'm not sure anymore with the hacks I've tried to work around :\
Yeah, I'm going to start over... thanks for the suggestions thus far..lbv wrote:
- Did you check your program against the sample cases given in the problem statement?
- Using a custom comparison method in next_permutation seems unnecessary. The order in which you generate the permutations don't have much importance if you end up placing the words in a set, which imposes its own order.
- The functor in compare seems incomplete. You don't have a return statement at the end of that function, which means that the compiler is free to return anything if it reaches that point. Try configuring your compiler so that it shows you all warnings, which can help you catch this type of bug.
- As you recognise, your code seems to have picked up a number of hacks along the way. That's never a good sign. I suggest you start from scratch, and try working out the problem in your head first until you're confident that you understand what the problem is asking for, and how to compute it. You'll notice that the solution doesn't require so much work and can be implemented succintly.
Code: Select all
cin >> word;
set<string> words;
//SORT(word);
do
{
words.insert(word);
debug(word, endl);
}
while (next_permutation(word.begin(), word.end()));
Code: Select all
1
aAb
Code: Select all
aAb
abA
bAa
baA
It doesn't skip them. It's just that next_permutation works by calculating the next permutation in lexicographical order. If you initially feed it a string that is not the lexicographically lowest permutation, it will not produce all permutations; no surprises there. For more details, read its documentation.mgavin2 wrote: What annoys me is if there are similar characters in next_permutation, it seems to skip them
If you decide to do it, go ahead, it shouldn't be much harder. However, I can tell you that I solved it using only next_permutation with a custom comparator, and a simple mechanism to avoid duplicates (no set).mgavin2 wrote:Maybe I should just skip next_permutation and recursively generate them by hand :\
Code: Select all
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int t, n;
string A;
bool cmp(char x, char y)
{
if (tolower(x) == tolower(y))
return isupper(x);
return tolower(x) < tolower(y);
}
int main()
{
//freopen("input", "r", stdin);
cin >> t;
while (t--)
{
cin >> A;
sort(A.begin(), A.end(), cmp);
do
{
cout << A << "\n";
}
while (next_permutation(A.begin(), A.end(), cmp));
}
return 0;
}
Code: Select all
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
char str[10000];
scanf("%s",str);
int l = strlen(str);
sort(str,str+l);
do
{
cout<<str<<endl;
}
while( next_permutation(str,str+l));
}
return 0;
}