195 - Anagram

[brianfry713]

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

[shikhorroy]

O...thanks.

[raihan_sust05]

i am already fed up with this anyone help me please

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;
}

thanks in advance

[brianfry713]

It looks like you figured it out.

[Angry Bird]

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 READ(f) freopen(f, "r", stdin)
#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]

Try running your code on the sample input.

[rloursua]

Please help me.
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]

Try the I/O in this thread.

[Aurango]

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]

http://acm.uva.es/board/viewtopic.php?t=70958

[Aurango]

http://acm.uva.es/board/viewtopic.php?t=70958

Sry,i dnt get anything..

[brianfry713]

Try running your code on the input I posted in that thread.

[uDebug]

Replying to follow the thread.

[fresher96]

hey guys
how about this trick it may help

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]

please help me......what is the problem in my code???? Every time getting Wrong Ans!!!!!!!

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;
}