## 195 - Anagram

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - Anagram(WA)

Input:

Code: Select all

1
AaBb
AC output:

Code: Select all

AaBb
AabB
ABab
ABba
AbaB
AbBa
aABb
aAbB
aBAb
aBbA
abAB
abBA
BAab
BAba
BaAb
BabA
BbAa
BbaA
bAaB
bABa
baAB
baBA
bBAa
bBaA
Check input and AC output for thousands of problems on uDebug!

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

### Re: 195 - Anagram(WA)

O...thanks.

raihan_sust05
New poster
Posts: 5
Joined: Fri Nov 22, 2013 6:34 pm

### WA in 195 - Anagram

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>

#define pi acos(0)
#define inf 1<<30
#define max 60
#define sz 60
#define true 1
#define false 0
#define pb(a) push_back(a)
#define size(e) (int)e.size()
#define clr(a,b) memset(a,b,sizeof(a))

typedef long long int ll;

using namespace std;
char  in[sz];
/* lch = lower case character, uch = uppercase character */

bool got[sz];

/* glch = is the lower character visited before, guch = is the uppercase character visited before */

int strln, n;
char out[sz];

void recur(int depth, int taken);
void order();

// FILE *fpt;
// fpt = fopen("tst.dat", "w");

int main()
{
//    freopen("195_in.txt", "r", stdin);
//    freopen("195_out.txt", "w", stdout);
int i, j, tst;

scanf("%d", &tst);

while(tst > 0)
{
scanf(" %s", in);

strln = strlen(in);

order();
clr(got, 0);
recur(0, 0);

--tst;
//        puts("");
}
return 0;
}

void recur(int depth, int taken)
{
int i = 0;

if(depth == strln)
{
out[strln] = '\0';
puts(out);
}

bool guch[sz], glch[sz];
clr(glch, 0);
clr(guch, 0);

/* glch  && guch is here to ensure that no repeatation is happened */

while(in[i] != '\0')
{
if(!got[i])
{
if(in[i] >= 'A' && in[i] <= 'Z')
{
if(!guch[in[i] - 'A'])
{
out[taken] = in[i];
guch[in[i] - 'A'] = true;
got[i] = true;
recur(depth + 1, taken + 1);
got[i] = false;
}

}

else if(in[i] >= 'a' && in[i] <= 'z')
{
if(!glch[in[i] - 'a'])
{
out[taken] = in[i];
glch[in[i] - 'a'] = true;
got[i] = true;
recur(depth + 1, taken + 1);
got[i] = false;
}
}
}

++i;
}

return;
}

void order()
{
int i, j;

for(i = 0; i < strln - 1; ++i)
{
for(j = i + 1; j < strln; ++j)
{
if((toupper(in[i]) == toupper(in[j])) &&(in[i] > in[j]))
swap(in[i], in[j]);
else if(toupper(in[i]) > toupper(in[j]))
swap(in[i], in[j]);
}
}
//    puts("");
//    puts("");
//    puts("");
return;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - Anagram

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Angry Bird
New poster
Posts: 21
Joined: Mon Apr 08, 2013 8:38 am

### Re: 195 - WA again and again

Why giving Output Limit?????

Code: Select all

#include <bits/stdc++.h>
using namespace std;

#define lop(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define mem(t) memset((t), 0, sizeof(t))
typedef long long int64;
typedef long double d64;
#define WRITE(f) freopen(f, "w", stdout)
#define PI 3.1415926535897932384626433832
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define bg begin
#define pf printf
#define sf scanf
#define inpc(ch) scanf("%c",&ch)
#define inp(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d%d",&x,&y)
#define Get(s) getline(cin,s)
#define Sort(v) sort(v.begin(),v.end());
#define out(x) printf("%d\n",x);
#define TC printf("Case %d: ",++cas);
#define TC1 printf("CASE# %d:\n",++cas);

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T sq(T n) { return n*n; }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }
template< class T > T power(T N,T P){ if(P==0) return 1; return (P==1)? N: N*power(N,P-1); }

char arr[100];
vector<char>result;
int taken[100],i;

void call(int n)
{
if(result.size()==n)
{
lop(i,n)
{
pf("%c",result[i]);
}
pf("\n");
return;
}

lop(i,n)
{
if(taken[i]==0)
{
taken[i]=1;
result.push_back(arr[i]);
call(n);
taken[i]=0;
result.pop_back();
}
}
}

int main()
{
mem(taken);
char ch;
int n;
inp(n);
string str;

lop(i,n)
{
cin>>str;
sort(str.begin(),str.end());

lop(j,str.size())
{
arr[j]=str[j];
}
call(str.size());
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - WA again and again

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

rloursua
New poster
Posts: 4
Joined: Tue Feb 11, 2014 5:52 pm

### Re: 195 - Anagram

I really have no idea why I'm getting WA.
I tried removing and placing back the blank link at the end of the output but both returned as WA

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>

int compare (const void * a, const void * b)
{
return (int)( *(char*)a - *(char*)b );
}

int main()
{
char letters[1024];
int wordSize = 0;
int cases = 0;
int i = 0;

scanf("%d",&cases);

for(i=0;i<cases;i++)
{
char orig[1024];
scanf("%s",letters);
int wordSize = strlen(letters);
qsort(letters,wordSize,sizeof(char),compare);
strcpy(orig,letters);
do
{
printf("%s\n",letters);
std::next_permutation(letters,letters+wordSize);
}
while(strcmp(letters,orig));

}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - Anagram

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

### 195 - Anagram?? why wrong answer???

my code for UVA 195 problem run well but showing wrong answer in uva online judge..plz help???

Code: Select all

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

class Main {

public static void main(String[] args)throws IOException {

Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
sc.nextLine();
String str;
char[] c;
while(test!=0)
{
str=sc.nextLine();
c=str.toCharArray();
Arrays.sort(c);
do{
System.out.println(c);
}while(nextPermutation(c));
test--;
}
}

static boolean nextPermutation(char[] array) {
int i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i == 0) {
return false;
}

int j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
char temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;

j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return true;
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - Anagram?? why wrong answer???

Check input and AC output for thousands of problems on uDebug!

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

### Re: 195 - Anagram?? why wrong answer???

Sry,i dnt get anything..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 195 - Anagram?? why wrong answer???

Try running your code on the input I posted in that thread.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 195 - Anagram

Check input and AC output for over 7,500 problems on uDebug!

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 195 - Anagram

hey guys

Code: Select all

int alph_ord(char c)
{
if(isupper(c))
{
return (c-'A')*2;
}
else
{
return (c-'a')*2+1;
}
}
bool cmp(const char &a,const char &b)
{
return alph_ord(a) < alph_ord(b);
}

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Re: 195 - Anagram!!!! WA

Code: Select all

#include<iostream>
#include<cstring>
#include<map>

using namespace std;

map <char,int>M;

void Swap (char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}

void lexicographical_Permutations(char str[],int n)
{
for(int i=0;i<n;i++) {

for(int j=i+1;j<n;j++) {

if(M[str[i]]>M[str[j]]) {
Swap(&str[i],&str[j]);
}
}
}
bool isFinished=false;
char temp;

while(!isFinished) {
cout<<str<<endl;

int i;
for (i=n-2;i>=0;--i ) {
if (M[str[i]]<M[str[i+1]]) break;
}

if(i==-1) isFinished=true;

else {

int j=n-1;
while(M[str[j]]<=M[str[i]]) j--;

Swap(&str[j],&str[i]);

j=n-1;
i=i+1;
while(i<j) {
Swap(&str[i],&str[j]);
i++;
j--;
}
}
}
}

int main()
{
char str[100];
int test;
M['A']=1;
M['a']=2;
M['B']=3;
M['b']=4;
M['C']=5;
M['c']=6;
M['D']=7;
M['d']=8;
M['E']=9;
M['e']=10;
M['F']=11;
M['f']=12;
M['G']=13;
M['g']=14;
M['H']=15;
M['h']=16;
M['I']=17;
M['i']=18;
M['J']=19;
M['j']=20;
M['K']=21;
M['k']=22;
M['L']=23;
M['l']=24;
M['m']=25;
M['m']=26;
M['N']=27;
M['n']=28;
M['O']=29;
M['o']=30;
M['P']=31;
M['p']=32;
M['Q']=33;
M['q']=34;
M['R']=35;
M['r']=36;
M['S']=37;
M['s']=38;
M['T']=39;
M['t']=40;
M['U']=41;
M['u']=42;
M['V']=43;
M['v']=44;
M['W']=45;
M['w']=46;
M['X']=47;
M['x']=48;
M['Y']=49;
M['y']=50;
M['Z']=51;
M['z']=52;

cin>>test;
while(test--) {
cin>>str;
int len=strlen(str);
lexicographical_Permutations(str,len);
}
return 0;
}