OJ Board

Posted: **Sun Feb 16, 2003 12:28 pm**

hmmm, I misunderstood the problem statement about the ascending order
thx red scorpion, now I know why I get WA.

only one problem lie now == > how to code it right

I tried to fix my code but still couldn't get the result as same as
your. can you tell me hints to solve this

Posted: **Sun Feb 16, 2003 4:17 pm**

right you are.

Posted: **Mon Feb 17, 2003 10:19 am**

Hi, Try to sort Acending A-a-B-b-C-c-D-d-E-e-...
using array, like this:

[code]
st['A'] = 1
st['a'] = 2
st['B'] = 3
st['b'] = 4
st['C'] = 5
st['c'] = 6

And using this array to sort the string.
Hope this helps.

[/code]

Posted: **Wed Apr 16, 2003 8:16 pm**

yeah. that's just the solution. i was getting WA because i've not noticed that particular question. now i've got AC.

Thanks everybody

Posted: **Sat Apr 26, 2003 8:39 pm**

I followed the same ascending order as u guys..but getting WA...

I don't find any error in my code..one problem may be in determining
the factorial of the length of the string...
I didn't find statement about what's the maximum size of the string..
please explain it to me...I used double to calculate factorial and converted it to unsigned long...is it right?
however, here's my code:

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 200
#define MAXSZ 60

int comp(const void *a,const void *b);
void permutation(long arr[],long n);
unsigned long fac(long n);

long m,to_div[MAX];
char letter[]={'0','A','a','B','b','C','c','D','d','E','e','F','f','G','g','H',
'h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R',
'r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
void main()
{

long n,a,len,i,j,count[MAX],num[MAX];
char str[MAX];

scanf("%ld",&n);
for(a=0;a<n;a++)
 {
 for(i=0;i<MAXSZ;i++)
   {
   count[i]=0;
   num[i]=0;
   }
 scanf("%s",str);
 len=strlen(str);

 for(i=0;i<len;i++)
   for(j=1;j<MAXSZ;j++)
      if(str[i]==letter[j])
        {
        num[i]=j;
        break;
        }


 for(i=0;i<len;i++)
   count[num[i]]++;

 j=0;
 for(i=1;i<MAXSZ;i++)
   if(count[i]>1)
      to_div[j++]=count[i];
 m=j;

 

 qsort((void *)num, len, sizeof(num[0]), comp);
 permutation(num,len);

 }
}

int comp(const void *a,const void *b)
{
  return (*(long *)a - *(long *)b);
}

void permutation(long arr[],long n)
{
long a,j,k,r,s;
unsigned long x,factorial;
long temp;
factorial=fac(n);

for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
for(x=1;x<factorial;x++)
 {
 j=n-2;
 while(arr[j]>=arr[j+1])
   j--;

 k=n-1;
 while(arr[j]>=arr[k])
   k--;

 temp=arr[j];
 arr[j]=arr[k];
 arr[k]=temp;

 r=n-1;
 s=j+1;
 while(r>=s)
   {
   temp=arr[r];
   arr[r]=arr[s];
   arr[s]=temp;

   r--;
   s++;
   }

 for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
 }

}

unsigned long fac(long n)
{
double pro;
long a,b;
unsigned long fact;

pro=1;
for(a=2;a<=n;a++)
  pro*=a;
for(a=0;a<m;a++)
  for(b=to_div[a];b>=2;b--)
   pro/=b;
fact=(unsigned long)pro;
return fact;
}

Posted: **Sat May 10, 2003 5:43 pm**

I would like to learn some efficient algorithms/methods to generate permutations and combinations.

When using my own algorithm, I always get TLE for both 195 and 10098......

Please, could anyone share their thoughts or algorithms with me?

It's hard for me to find related online resources, as I know nothing about programming languages other than Pascal.

So please help!!!

Or, you may introduce some good books or resources to me.

Thanks very much!!

Posted: **Sat May 10, 2003 9:26 pm**

I use algorithm for finding next permutation of some sequence A. Let n denote length of A. Find such A and A[j] elements that satisfy condition A < A[j], where i < j. If there are no such two elements, there is no next permutation. Otherwise, exchange these two elements and reverse order of elements A[i + 1] through A[n], i.e. A[i + 1] <-> A[n], A[i + 2] <-> A[n

Posted: **Sun Jun 01, 2003 10:49 pm**

Try http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz. This is a preview on a chapter on permutations in Knuth's Art of Computer Programming. Should be the definite guide

Posted: **Mon Jun 02, 2003 1:16 am**

I just like to point out an alternative to using the array with st[0] = 'A', st[1] = 'a', etc. I would recommend a function, like this one:

bool isLower(char a, char b)
{
if (tolower(a) == tolower(b)) return (a < b);
else return (tolower(a) < tolower(b));
}

It gives the order you're looking for, and is (in my opinion) cleaner programming.

Posted: **Thu Jun 05, 2003 7:21 pm**

Hi try to search SEPA algoithm on the net resources

Posted: **Fri Jun 06, 2003 3:02 am**

Thx for all your help!

Now I know how to generate permutations in reasonable time! Thx a lot!

For folks trying to solve Q195, be careful:
the order of the letters is
A -> a -> B -> b -> C -> c -> ... -> Z -> z

Posted: **Sat Jul 19, 2003 2:08 pm**

The judge's input positively more than 30 chars...my mistake was the size of the array was too small.

Thanks guys,
nick

Posted: **Wed Aug 06, 2003 2:33 am**

Here is quite efficient (I think) and easy-to-use function that helps to sort characters correctly:

[pascal]
function letval(c:char):integer;
var v:integer;
begin
if upcase(c)=c then
v:=(ord(c)-ord('A'))*2
else
v:=(ord(c)-ord('a'))*2+1;
letval:=v;
end;
[/pascal]

It generates character codes this way: A=0, a=1, B=2, etc.. and they are easy to sort...

Posted: **Sun Nov 23, 2003 4:47 am**

Why OLE?

My code:

Code: Select all

[cpp]
#include <iostream.h>
#include <string.h>

char A[100], escreve[100], temp;
int n, marca[1000], cont;

void anagrama()
{
    for (int i=0; i<strlen(A); i++)
     { if (marca[i]==0)
        { escreve[cont]=A[i];
	       cont++;
	       marca[i]=1;
	       if (cont==strlen(A))
	        { escreve[cont]='\0';
	          cout << escreve << endl;
	        }
          anagrama();
	  	 	 marca[i]=0;
	  		 cont--;
        }
    }
}

void main()
{
    cin >> n;

    for (int i=1; i<=n; i++)
    {
		cin >> A;
		for (int c=0; c<1000; c++) marca[c]=0;
      cont=0;

      for (int i=0; i<strlen(A)-1; i++)
       for (int j=i+1; j<strlen(A); j++)
        if (A[j]<A[i])
         { temp=A[j]; A[j]=A[i]; A[i]=temp; }
       anagrama();
    }
}
[/cpp]

Thanks.

Posted: **Wed Dec 03, 2003 2:25 am**

Hi guys, so I submitted like 10 times already and still getting WA for 195. I understand the sorting is A < a < B < b < C < c...and my code also takes care of blank lines. So here is my code, if anyone can kindly test it against some tricky inputs that would be great. Thanks in advance!

[cpp]/* 195 */
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

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);
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;
if(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);
for(int k=0; k<len-pos1-1; k++)
result+=temp2[k];
}
return result;
}

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;
}[/cpp]

OJ Board

195 - Anagram

195 : how to generate fast, sorted permutations/combinations

Next permutation

Text on permutations

yes indeed

Function for correct character sorting (195 - Anagram)

195 - OLE

another 195 WA... (already read all other posts)