OJ Board

The Online Judge board
https://onlinejudge.org/board/

195 - Anagram

https://onlinejudge.org/board/viewtopic.php?t=70958

Page 6 of 17

Posted: Wed Dec 03, 2003 3:59 am
by Nikolay Archak
Hi!

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 :D

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

Posted: Wed Dec 03, 2003 8:14 pm
by stcheung
Haha yes I wrote the lessthan function but only used it in the initial sorting and not in the next() function itself. The fact that it gave me correct output for sample data discouraged me from checking my code. Thank you so much for your detailed response and suggestions.

WA Help SOS SOS

Posted: Mon Jan 05, 2004 12:53 am
by aakash_mandhar
What is wrong with this code.. I thought this is a cool logic to generate next higher number.. Plz help

Thx in advance
[cpp]

# include<iostream.h>
# include<string.h>

char str[10000];
int a[10000];
int i,n,temp,len;
int nt;
int j;

int main()
{
cin>>nt;
while(nt--)
{
cin>>str;
len=strlen(str);

for(i=0;i<len;i++)
{
if(str>='A' && str<='Z') a=2*str;
if(str>='a' && str<='z') a=2*str+1;
}

for(i=0;i<len;i++)
{
for(j=0;j<len-i-1;j++)
{
if(a[j]>a[j+1])
{
a[j+1]=a[j]^a[j+1];
a[j]=a[j]^a[j+1];
a[j+1]=a[j]^a[j+1];
str[j+1]=str[j]^str[j+1];
str[j]=str[j]^str[j+1];
str[j+1]=str[j]^str[j+1];
}
}
}

for(int i1=0;i1<len;i1++) cout<<str[i1];
cout<<"\n";


n=len-1;
while(n!=0)
{
if(a[n]>a[n-1])
{
i=len-1;
while(a<=a[n-1]) i--;
str[n-1]=str^str[n-1];
str[i]=str[i]^str[n-1];
str[n-1]=str[i]^str[n-1];
a[n-1]=a[i]^a[n-1];
a[i]=a[i]^a[n-1];
a[n-1]=a[i]^a[n-1];
for(i=0;i<(len-n)/2;i++){str[n+i]=str[n+i]^str[len-1-i];str[len-1-i]=str[n+i]^str[len-1-i];str[n+i]=str[n+i]^str[len-1-i];a[n+i]=a[n+i]^a[len-1-i];a[len-1-i]=a[n+i]^a[len-1-i];a[n+i]=a[n+i]^a[len-1-i];}
n=len-1;
for(int i1=0;i1<len;i1++) cout<<str[i1];
cout<<"\n";
}
else n--;
}
}
return 1;
}

[/cpp]

Posted: Mon Jan 05, 2004 10:27 am
by shamim
You algoritm is correct, but if you carefully read the problem statement, you will discover that the ordering is
AaBbCc..........Zz and not ABC....abc. :wink:

Taken care of A a B b

Posted: Mon Jan 05, 2004 7:18 pm
by aakash_mandhar
HI shamim,
I guess my code takes care of that.
for 'A' to 'Z' value is 2*str
for 'a' to 'z' value is 2*str+1

So that cares of interleaving i guess..

So could u plz send me a test case where the output is wrong..

Thx
Aakash

195: Anagram Time Limit Exceeded

Posted: Wed Jan 07, 2004 4:05 am
by wamorimjr
Could anyone help me? I have submited my algorithm but I always have a Time Limit Exceed message. I'll send my code:

[c]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define MAX_LEN 10
#define MAX_ARRAY 100000
#define TRUE 1
#define FALSE 0

long cont;

/*---------------------------------------------------*/
/* Compara dois caracteres retornando: */
/* 0 Se o caracter 1 e igual a 2 */
/* -1 Se o caracter 1 e menor que o 2 */
/* 1 Se o caracter 1 e maior que o 2 */
/*---------------------------------------------------*/
int CompararChar(char cChar1, char cChar2)
{
char cTemp1 = tolower(cChar1);
char cTemp2 = tolower(cChar2);

if(cTemp1 < cTemp2)
return -1;
else if(cTemp1 > cTemp2)
return 1;
else
{
if (islower(cChar1))
{
/* Se os caracteres 1 e 2 sao lowercase eles sao iguais */
if (islower(cChar2))
return 0;
/* Se o caracter 1 e lowercase e o 2 e uppercase */
/* 1 e maior que 2 */
else
return 1;
}
else
{
/* Se os caracteres 1 e 2 sao uppercase eles sao iguais */
if (isupper(cChar2))
return 0;
/* Se o caracter 1 e uppercase e o 2 e lowercase */
/* 1 e menor que 2 */
else
return -1;
}
}
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
int Comparar(char *pcString1, char *pcString2)
{
int iComp;
/* Obtem o tamanho das strings a serem comparadas */
int iLen1 = strlen(pcString1);
int iLen2 = strlen(pcString2);

for(;pcString1 && pcString2; pcString1++, pcString2++)
{
if (!pcString1[0] && !pcString2[0]) return 0;

/*Compara os caracteres correntes das duas string */
iComp = CompararChar(*pcString1, *pcString2);

/* Caso o os carateres correntes sejam diferentes, */
/* retornar indicando se a string 1 e maior ou menor */
/* que a string 2*/
if (iComp)
return iComp;
}

/* Se as strings tem o mesmo tamanho elas sao iguais */
if (iLen1 == iLen2)
return 0;
/* Se a string 1 e menor que a 2 */
else if (iLen1 < iLen2)
return -1;
/* Se a string 1 e maior que a 2 */
else
return 1;
}


void QuickSort(char ppVetor[MAX_ARRAY][MAX_LEN], int iIni, int iFim)
{
int iEsq, iDir;
char *pItem;
char pTemp[MAX_LEN];

if( iFim > iIni ) /* i.e. at least 2 elements, then */
{
iEsq = iIni;
iDir = iFim;
pItem = ppVetor[iIni]; /* NB. just an estimate! */

while(iDir >= iEsq) /* partition a[lo..hi] */
/* a[lo..iEsq-1]<=median and a[iDir+1..hi]>=median */
{
while(Comparar(ppVetor[iEsq], pItem) == -1) iEsq++;
/* a[iEsq] >= median */

while(Comparar(ppVetor[iDir], pItem) == 1) iDir--;
/* a[iEsq] >= median >= a[iDir] */

if(iEsq > iDir) break;

/*swap:*/
strcpy(pTemp, ppVetor[iEsq]);
strcpy(ppVetor[iEsq], ppVetor[iDir]);
strcpy(ppVetor[iDir], pTemp);
iEsq++;
iDir--;
}
/* a[lo..iEsq-1]<=median and a[iDir+1..hi]>=median
and iEsq > iDir */

QuickSort(ppVetor, iIni, iDir);/* divide and conquer */
QuickSort(ppVetor, iEsq, iFim);
}
}/*quicksort*/


void Sort(char ppVetor[MAX_ARRAY][MAX_LEN], int iLen)
{
if (iLen <= 0) return;

QuickSort(ppVetor, 0, iLen - 1);
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
long GerarPermutacao(char palavra[MAX_LEN], int i, int n, char lista[MAX_ARRAY][MAX_LEN])
{
int j = 0, s=0, x=0;
char temp;
if (i == n-1)
{
strcpy(lista[cont],palavra);
Sort(lista, cont);
cont++;
}
else
{
for(j=i; j<n; j++)
{
temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
x = GerarPermutacao(palavra,i+1,n, lista);

temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
}
}
return(cont);
}

void Imprimir(char ppLista[MAX_ARRAY][MAX_LEN], int iLen)
{
int iIndice = 0;
int iIgual = FALSE;

for (iIndice = 0; iIndice < iLen; iIndice++)
{
if (!iIndice)
iIgual = FALSE;
else
{
if (strcmp(ppLista[iIndice], ppLista[iIndice-1]))
iIgual = FALSE;
else
iIgual = TRUE;
}

if (!iIgual)
{
char *p;
p = ppLista[iIndice];
printf("%s\n", p);
}
}
}

void main()
{
int iQtde;
int iQtdeComb = 0;
int iIndice = 0;
char pPalavra[MAX_LEN];
char ppLista[MAX_ARRAY][MAX_LEN];

#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

scanf("%d", &iQtde);

for (iIndice = 0; iIndice < iQtde; iIndice++)
{
scanf("%s", pPalavra);

cont = 0;

iQtdeComb = GerarPermutacao(pPalavra, 0, strlen(pPalavra), ppLista);

Sort(ppLista, iQtdeComb);

Imprimir(ppLista, iQtdeComb);
}
}
[/c]

Posted: Wed Jan 07, 2004 10:57 am
by shamim
I have given the follwing input to your program, after compiliing it with VC++.
  • abcdefg
The program runs for few seconds and then crashes. I did not check your algo., but u can try to debug your code using this input.

195 : Runtime Error (SIGSEGV)

Posted: Fri Jan 09, 2004 2:13 am
by wamorimjr
Shamin,
I did some changes in my code but now I got a "Runtime Error (SIGSEGV)" message. I think that the problem is because the length of the word used by judge is >9.
For a length word = 10 I need a vector length of 3628800, but if try to declare this vector I have a "Runtime Error (SIGSEGV)" before I try to execute the code.
Could you help me?

[c]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define MAX_LEN 12
#define MAX_ARRAY 500000
#define TRUE 1
#define FALSE 0

long cont;

/*---------------------------------------------------*/
/* Compara dois caracteres retornando: */
/* 0 Se o caracter 1 e igual a 2 */
/* -1 Se o caracter 1 e menor que o 2 */
/* 1 Se o caracter 1 e maior que o 2 */
/*---------------------------------------------------*/
int CompararChar(char cChar1, char cChar2)
{
char cTemp1 = tolower(cChar1);
char cTemp2 = tolower(cChar2);

if(cTemp1 < cTemp2)
return -1;
else if(cTemp1 > cTemp2)
return 1;
else
{
if (islower(cChar1))
{
/* Se os caracteres 1 e 2 sao lowercase eles sao iguais */
if (islower(cChar2))
return 0;
/* Se o caracter 1 e lowercase e o 2 e uppercase */
/* 1 e maior que 2 */
else
return 1;
}
else
{
/* Se os caracteres 1 e 2 sao uppercase eles sao iguais */
if (isupper(cChar2))
return 0;
/* Se o caracter 1 e uppercase e o 2 e lowercase */
/* 1 e menor que 2 */
else
return -1;
}
}
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
int Comparar(char *pcString1, char *pcString2)
{
int iComp;
/* Obtem o tamanho das strings a serem comparadas */
int iLen1 = strlen(pcString1);
int iLen2 = strlen(pcString2);

for(;pcString1 && pcString2; pcString1++, pcString2++)
{
if (!pcString1[0] && !pcString2[0]) return 0;

/*Compara os caracteres correntes das duas string */
iComp = CompararChar(*pcString1, *pcString2);

/* Caso o os carateres correntes sejam diferentes, */
/* retornar indicando se a string 1 e maior ou menor */
/* que a string 2*/
if (iComp)
return iComp;
}

/* Se as strings tem o mesmo tamanho elas sao iguais */
if (iLen1 == iLen2)
return 0;
/* Se a string 1 e menor que a 2 */
else if (iLen1 < iLen2)
return -1;
/* Se a string 1 e maior que a 2 */
else
return 1;
}

void DownHeap(char ppVetor[MAX_ARRAY][MAX_LEN], long lIni, long lFim)
/* PRE: a[k+1..N] is a heap */
/* POST: a[k..N] is a heap */
{
long lFilho;
char pItem[MAX_LEN];

strcpy(pItem, ppVetor[lIni]);

while (lIni <= lFim/2) /* k has child(s) */
{
lFilho = 2*lIni;

/* pick larger child */
if(lFilho < lFim && Comparar(ppVetor[lFilho], ppVetor[lFilho + 1]) == -1)
lFilho++;

if(Comparar(pItem, ppVetor[lFilho]) >= 0)
break;

/* else */
strcpy(ppVetor[lIni], ppVetor[lFilho]); /* move child up */

lIni = lFilho;
}

strcpy(ppVetor[lIni], pItem);
}/*downHeap*/

void HeapSort(char ppVetor[MAX_ARRAY][MAX_LEN], long lLen)
/* sort a[1..N], N.B. 1 to N */
{
long lIndice;
char pTemp[MAX_LEN];

for(lIndice = lLen / 2; lIndice >= 0; lIndice--)
DownHeap(ppVetor, lIndice, lLen);
/* a[1..N] is now a heap */

for(lIndice = lLen; lIndice > 0; lIndice--)
{
memcpy(pTemp, ppVetor[lIndice], MAX_LEN);
memcpy(ppVetor[lIndice], ppVetor[0], MAX_LEN); /* largest of a[1..i] */
memcpy(ppVetor[0], pTemp, MAX_LEN);

DownHeap(ppVetor, 0, lIndice - 1); /* restore a[1..i-1] heap */
}
}/*heapSort*/


void Sort(char ppVetor[MAX_ARRAY][MAX_LEN], int iLen)
{
if (iLen <= 0) return;

HeapSort(ppVetor, iLen - 1);
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
long GerarPermutacao(char palavra[MAX_LEN], int i, int n, char lista[MAX_ARRAY][MAX_LEN])
{
int j = 0, s=0, x=0;
char temp;
if (i == n-1)
{
strcpy(lista[cont],palavra);
cont++;
}
else
{
for(j=i; j<n; j++)
{
temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
x = GerarPermutacao(palavra,i+1,n, lista);

temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
}
}
return(cont);
}

void Imprimir(char ppLista[MAX_ARRAY][MAX_LEN], int iLen)
{
int iIndice = 0;
int iIgual = FALSE;

for (iIndice = 0; iIndice < iLen; iIndice++)
{
if (!iIndice)
iIgual = FALSE;
else
{
if (strcmp(ppLista[iIndice], ppLista[iIndice-1]))
iIgual = FALSE;
else
iIgual = TRUE;
}

if (!iIgual)
{
char *p;
p = ppLista[iIndice];
printf("%s\n", p);
}
}
}

void main()
{
int iQtde;
int iQtdeComb = 0;
int iIndice = 0;
char pPalavra[MAX_LEN];
char ppLista[MAX_ARRAY][MAX_LEN];

#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

scanf("%d", &iQtde);

for (iIndice = 0; iIndice < iQtde; iIndice++)
{
scanf("%s", pPalavra);

cont = 0;

iQtdeComb = GerarPermutacao(pPalavra, 0, strlen(pPalavra), ppLista);

Sort(ppLista, iQtdeComb);

Imprimir(ppLista, iQtdeComb);
}
}
[/c]

Posted: Fri Jan 09, 2004 6:17 am
by junbin
I don't really understand your code since most of it is not in English.. :p But here's what I think:

1) Character comparison is too slow. Simply compare by ASCII values is a lot faster.

2) Don't treat strings as arrays, treat them as pointers, so increment pointers instead of incrementing indices. that's a lot faster too.

3) I believe you are generating all possible permutations, store them, then sort them, then print them. This is wasteful.. a simple hint: You do not need to store them if you organise that starting data.

195 : Runtime Error

Posted: Mon Jan 12, 2004 3:40 am
by wamorimjr
Could someone help me? I'm getting a Runtime Error from judge but I don't know why. Any idea?

[c]

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define MAX_LEN 12
#define MAX_ARRAY 40321
#define TRUE 1
#define FALSE 0

long cont;

/*---------------------------------------------------*/
/* Compara dois caracteres retornando: */
/* 0 Se o caracter 1 e igual a 2 */
/* -1 Se o caracter 1 e menor que o 2 */
/* 1 Se o caracter 1 e maior que o 2 */
/*---------------------------------------------------*/
int CompararChar(char cChar1, char cChar2)
{
char cTemp1 = tolower(cChar1);
char cTemp2 = tolower(cChar2);

if(cTemp1 < cTemp2)
return -1;
else if(cTemp1 > cTemp2)
return 1;
else
{
if (islower(cChar1))
{
/* Se os caracteres 1 e 2 sao lowercase eles sao iguais */
if (islower(cChar2))
return 0;
/* Se o caracter 1 e lowercase e o 2 e uppercase */
/* 1 e maior que 2 */
else
return 1;
}
else
{
/* Se os caracteres 1 e 2 sao uppercase eles sao iguais */
if (isupper(cChar2))
return 0;
/* Se o caracter 1 e uppercase e o 2 e lowercase */
/* 1 e menor que 2 */
else
return -1;
}
}
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
int Comparar(char *pcString1, char *pcString2)
{
int iComp;
/* Obtem o tamanho das strings a serem comparadas */
int iLen1 = strlen(pcString1);
int iLen2 = strlen(pcString2);

for(;pcString1 && pcString2; pcString1++, pcString2++)
{
if (!pcString1[0] && !pcString2[0]) return 0;

/*Compara os caracteres correntes das duas string */
iComp = CompararChar(*pcString1, *pcString2);

/* Caso o os carateres correntes sejam diferentes, */
/* retornar indicando se a string 1 e maior ou menor */
/* que a string 2*/
if (iComp)
return iComp;
}

/* Se as strings tem o mesmo tamanho elas sao iguais */
if (iLen1 == iLen2)
return 0;
/* Se a string 1 e menor que a 2 */
else if (iLen1 < iLen2)
return -1;
/* Se a string 1 e maior que a 2 */
else
return 1;
}

void DownHeap(char ppVetor[MAX_ARRAY][MAX_LEN], long lIni, long lFim)
/* PRE: a[k+1..N] is a heap */
/* POST: a[k..N] is a heap */
{
long lFilho;
char pItem[MAX_LEN];

strcpy(pItem, ppVetor[lIni]);

while (lIni <= lFim/2) /* k has child(s) */
{
lFilho = 2*lIni;

/* pick larger child */
if(lFilho < lFim && Comparar(ppVetor[lFilho], ppVetor[lFilho + 1]) == -1)
lFilho++;

if(Comparar(pItem, ppVetor[lFilho]) >= 0)
break;

/* else */
strcpy(ppVetor[lIni], ppVetor[lFilho]); /* move child up */

lIni = lFilho;
}

strcpy(ppVetor[lIni], pItem);
}/*downHeap*/

void HeapSort(char ppVetor[MAX_ARRAY][MAX_LEN], long lLen)
/* sort a[1..N], N.B. 1 to N */
{
long lIndice;
char pTemp[MAX_LEN];

for(lIndice = lLen / 2; lIndice >= 0; lIndice--)
DownHeap(ppVetor, lIndice, lLen);
/* a[1..N] is now a heap */

for(lIndice = lLen; lIndice > 0; lIndice--)
{
memcpy(pTemp, ppVetor[lIndice], MAX_LEN);
memcpy(ppVetor[lIndice], ppVetor[0], MAX_LEN); /* largest of a[1..i] */
memcpy(ppVetor[0], pTemp, MAX_LEN);

DownHeap(ppVetor, 0, lIndice - 1); /* restore a[1..i-1] heap */
}
}/*heapSort*/


void Sort(char ppVetor[MAX_ARRAY][MAX_LEN], int iLen)
{
if (iLen <= 0) return;

HeapSort(ppVetor, iLen - 1);
}

/*---------------------------------------------------*/
/* Compara duas strings retornando: */
/* 0 Se a string 1 e igual a 2 */
/* -1 Se a string 1 e menor que a 2 */
/* 1 Se a string 1 e maior que a 2 */
/*---------------------------------------------------*/
long GerarPermutacao(char palavra[MAX_LEN], int i, int n, char lista[MAX_ARRAY][MAX_LEN])
{
int j = 0, s=0, x=0;
char temp;
if (i == n-1)
{
strcpy(lista[cont],palavra);
cont++;
}
else
{
for(j=i; j<n; j++)
{
temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
x = GerarPermutacao(palavra,i+1,n, lista);

temp = palavra;
palavra = palavra[j];
palavra[j] = temp;
}
}
return(cont);
}

void Imprimir(char ppLista[MAX_ARRAY][MAX_LEN], int iLen)
{
int iIndice = 0;
int iIgual = FALSE;

for (iIndice = 0; iIndice < iLen; iIndice++)
{
if (!iIndice)
iIgual = FALSE;
else
{
if (strcmp(ppLista[iIndice], ppLista[iIndice-1]))
iIgual = FALSE;
else
iIgual = TRUE;
}

if (!iIgual)
{
char *p;
p = ppLista[iIndice];
printf("%s\n", p);
}
}
}

void main()
{
int iQtde;
int iQtdeComb = 0;
int iIndice = 0;
char pPalavra[MAX_LEN];
char ppLista[MAX_ARRAY][MAX_LEN];

#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

scanf("%d", &iQtde);

for (iIndice = 0; iIndice < iQtde; iIndice++)
{
scanf("%s", pPalavra);

cont = 0;

iQtdeComb = GerarPermutacao(pPalavra, 0, strlen(pPalavra), ppLista);

Sort(ppLista, iQtdeComb);

Imprimir(ppLista, iQtdeComb);
}
}
[/c]

how to speed up 195

Posted: Thu Feb 19, 2004 4:48 pm
by harshahs
hello,

I am using Disjkastra's algorithm to generate the permutations of the given string in lexicographical ( dictonary ) order. But it is taking a lot of time when the string length exceeds 8.

Can u guys help me in speeding up my program.
[c]
#include <stdio.h>
#include <string.h>

int main(void)
{
unsigned n;
char str[20],tstr[21];
unsigned register x,i,j,r,s,len;

scanf("%u",&n);

for(x=0;x<n;x++)
{
memset((void *)str,0,sizeof(str));
scanf("%s",str);

for(i=0;i<strlen(str)-1;i++)
{
for(j=i+1;j<strlen(str);j++)
{
if(str > str[j])
{
str ^= str[j] ^= str ^= str[j];
}
}
}

memset((void *)tstr,0,sizeof(tstr));

tstr[0] = 0;

j=1;
tstr[j++] = str[0];

for(i=1;i<strlen(str);i++)
tstr[j++] = str;

i = 1;
len = strlen(str);
while (i)
{
for (i=1; i <= len; i++)
printf("%c", tstr);
printf("\n");

i = len-1;
while (tstr >= tstr[i+1]) i--;

j = len;
while (tstr >= tstr[j]) j--;

tstr ^= tstr[j] ^= tstr ^= tstr[j];

r = len;
s = i+1;

while (r > s)
{
tstr[r] ^= tstr[s] ^= tstr[r] ^= tstr[s];
r--; s++;
}
}
}
return 0;
}
[/c]

Thank You
Harsha

Posted: Fri Feb 20, 2004 12:13 am
by junbin
tstr ^= tstr[j] ^= tstr ^= tstr[j];
looks cool
but

t = tstr
tstr = tstr[j]
tstr = t

is faster usually


but that's not the point. :) The point is that given the string, you should be able to generate immediately without computation.. in other words, your algorithm is wrong.

Posted: Fri Feb 20, 2004 7:46 am
by harshahs
Can you give me more hints on how to generate the string, without any computations.

Posted: Fri Feb 20, 2004 8:31 am
by junbin
harshahs wrote:Can you give me more hints on how to generate the string, without any computations.
You can just loop through all the possible combinations..

ie:

with the letters GBCFADE

the first combination is
ABCDEFG

the second is

ABCDEGF

Posted: Fri Feb 20, 2004 9:11 am
by harshahs
I think that is what I am doing in the loop
while(i)
{
...
}

before that I am just sorting the string so that if the input is
baca
i will begin the loop with the string aabc.
All times are UTC+02:00
Page 6 of 17

Powered by phpBB® Forum Software © phpBB Limited