Page 1 of 1

10063 - Knuth's Permutation

Posted: Tue Dec 10, 2002 2:22 pm
by stcheung
Anyone got an idea what's wrong with my program? It seems to work for sample input perfectly well. Thanks for any help/suggestion.


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

void permu(string, string);

int main()
{
string input;
while(true)
{
cin >> input;
if(cin.eof())
break;
permu(input, "");
cout << "\n";
}
return 0;
}

void permu(string input, string sofar)
{
if(input == "")
cout << sofar << "\n";
else
{
char ch = input[0];
string newinput, newsofar;
for(int i=0; i<sofar.length() + 1; i++)
{
newinput = input.substr(1, input.length() - 1);
newsofar = (sofar.substr(0, i) + ch +
sofar.substr(i, sofar.length()-i));
permu(newinput, newsofar);
}
}
}[/cpp]

Posted: Sat Dec 14, 2002 12:47 pm
by Larry
Simple changes can be made to accomodate a string with size 0... =)

your >> skips right over it.

10063 Knuth's Permutation again

Posted: Mon Jan 13, 2003 1:20 pm
by stcheung
I really am fed up with why my program still get WA. I have no idea at all what's wrong. Can anyone give me some help please...

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

void permu(string, string);
string removeblanks(string);

int main()
{
string input;
while(true)
{
getline(cin, input);
if(cin.eof())
break;
if(input != "")
{
permu(removeblanks(input), "");
cout << "\n";
}
}
return 0;
}

void permu(string input, string sofar)
{
if(input == "")
cout << sofar << "\n";
else
{
char ch = input[0];
string newinput, newsofar;
for(int i=0; i<sofar.length() + 1; i++)
{
newinput = input.substr(1, input.length() - 1);
newsofar = (sofar.substr(0, i) + ch +
sofar.substr(i, sofar.length()-i));
permu(newinput, newsofar);
}
}
}

string removeblanks(string in)
{
string result = "";
for(int i=0; i<in.length(); i++)
{
if(isalnum(in))
result+=in;
}
return result;
}[/cpp]

Posted: Tue Mar 11, 2003 4:27 am
by Red Scorpion

Code: Select all

Input :
ADCFG

Output:
GFCDA
FGCDA
FCGDA
FCDGA
FCDAG
GCFDA
CGFDA
CFGDA
CFDGA
CFDAG
GCDFA
CGDFA
CDGFA
CDFGA
CDFAG
GCDAF
CGDAF
CDGAF
CDAGF
CDAFG
GFDCA
FGDCA
FDGCA
FDCGA
FDCAG
GDFCA
DGFCA
DFGCA
DFCGA
DFCAG
GDCFA
DGCFA
DCGFA
DCFGA
DCFAG
GDCAF
DGCAF
DCGAF
DCAGF
DCAFG
GFDAC
FGDAC
FDGAC
FDAGC
FDACG
GDFAC
DGFAC
DFGAC
DFAGC
DFACG
GDAFC
DGAFC
DAGFC
DAFGC
DAFCG
GDACF
DGACF
DAGCF
DACGF
DACFG
GFCAD
FGCAD
FCGAD
FCAGD
FCADG
GCFAD
CGFAD
CFGAD
CFAGD
CFADG
GCAFD
CGAFD
CAGFD
CAFGD
CAFDG
GCADF
CGADF
CAGDF
CADGF
CADFG
GFACD
FGACD
FAGCD
FACGD
FACDG
GAFCD
AGFCD
AFGCD
AFCGD
AFCDG
GACFD
AGCFD
ACGFD
ACFGD
ACFDG
GACDF
AGCDF
ACGDF
ACDGF
ACDFG
GFADC
FGADC
FAGDC
FADGC
FADCG
GAFDC
AGFDC
AFGDC
AFDGC
AFDCG
GADFC
AGDFC
ADGFC
ADFGC
ADFCG
GADCF
AGDCF
ADGCF
ADCGF
ADCFG
Hope this helps. :lol: :lol:

Posted: Tue Mar 11, 2003 11:23 am
by Hisoka
Thanks red scorpion, I know this rule now, and my solution before is WA. :oops:

10063

Posted: Sun Apr 06, 2003 11:59 am
by oXy
I keep getting WA while trying to solve 10063. I am sure that my algorithm is correct and the problem must be the tricky input/output.

Here is my code. Hope someone who got AC helps me out here. Thanks.

[c]
#include <stdio.h>
#include <string.h>
#include <ctype.h>

void process(char *);
void normalize(char *);

int main(void)
{
char str[1024];
/* int t, T;*/

/* scanf("%d\n", &T);
for (t = 0; t < T; t++)
{*/
fgets(str, 1023, stdin);
while (!feof(stdin))
{
normalize(str);
process(str);
printf("\n");
fgets(str, 1023, stdin);
}
/*}*/

return 0;
}

void process(char *str)
{
int len = strlen(str);
int fact[16], fact_rev[16];
int i, j, k, l;
char buffer[10];

if (len == 0) return;

fact[0] = fact[1] = 1;
for (i = 2; i <= 10; i++)
fact = fact * i;
fact_rev[0] = 1;
fact_rev[1] = len;
for (i = 2; i <= len; i++)
fact_rev = fact_rev * (len - i + 1);

for (i = 0; i < fact[len]; i++)
{
memset(buffer, 0, sizeof(buffer));
for (j = 0; j < len; j++)
{
k = (i / fact_rev[j]) % (len - j);
for (l = 0; l < len; l++)
if (buffer[l] == 0)
{
if (k == 0)
{
buffer[l] = str[len - j - 1];
break;
}
else
k--;
}
}
printf("%s\n", buffer);
}
}

void normalize(char *str)
{
char buffer[1024];
char *c;
int len;

/* c = strchr(str, '\n');
if (c) *c = 0;
c = strchr(str, '\r');
if (c) *c = 0;*/

for (c = str, len = 0; *c; c++)
{
if (isalpha((*c)) || isdigit((*c)))
buffer[len++] = *c;
}
buffer[len] = 0;
memcpy(str, buffer, 1024 * sizeof(char));
}
[/c]

Posted: Tue Apr 08, 2003 5:10 pm
by Hisoka
Hello stefan, I'm sorry because I'm not check my mail for several day. I read your code, your algo is true, but your mistake only at your input.
I mean like this:

Code: Select all

while(gets(str)){
...
...
}
for another problem if input is terminated by EOF you can try this. :wink:

Posted: Thu Apr 10, 2003 3:28 pm
by oXy
10x, i got AC now.

But I still can't tell what the difference between

while (gets(str))
{
}

and

fgets(...)
while (!feof())
{
...
fgets(...);
}

is.

Posted: Tue Apr 29, 2003 9:34 pm
by yiuyuho
I believe this is a problem of the specification of the problem:

The Judges input is in fact something like:

<input1>
<input2>
.
.
.
<last_input>(EOF)

note that the eof is right after the last input, there is no '\n' to terminate the last output .

using while(!EOF), the program will not take the last input and thus resulted the last block of output missing

Posted: Fri Dec 02, 2005 8:39 am
by mamun
I don't understand how the permutation is done. Can anybody explain how the output of

Code: Select all

abc
is

Code: Select all

cba
bca
bac
cab
acb
abc
Thanks

Posted: Fri Jul 28, 2006 3:03 am
by Darko
Heh, a bit late, but what do they say? "better late..."

Anyway, you have to build it starting with the first element then adding others as explained (recursively inserting next one into all previous ones). And you display only permutations of size n (3 in this case)

So you have
zero elements:

one element:
a

two elements:
ba
ab

three elements:
(from ba)
cba
bca
bac
(from ab)
cab
acb
abc

For four, you would take each permutation from above and insert d in all positions:
(from cba)
dcba
cdba
cbda
cbad
(from bca)
dbca
bdca
bcda
bcad
...
(notice the pattern)

I hope this helps someone (took me a while to get a hang of it, now I get MLE - no idea why - I use 3.6 MB for the table.


<rant>
Well, it's 3.6 MB on paper, not sure how it translates using gcj - it works for me using -Xmx12m (limit is 16MB, with that switch I set JVM to use 12MB heap). This is on top of me failing to even read a file last night, pisses me off.

I don't know... most schools teach Java and its use is discouraged everywhere I look. Last regionals we were told half-jokingly that it's not a programming language and then they didn't even set the environment properly. And then they explained it with "I told you so". On top of that pc^2 by default gives WA for CE and TLE, that sort of thing...meh.

When I saw that SPOJ supported Java 1.5 I was all happy, then I realized half of the problems needed some sort of optimized I/O in order to pass. Meaning that I/O I use here is too slow for them. I am not going to rewrite I/O package just so I... oh, well, sorry about this, had to vent somewhere.
</rant>

Posted: Wed Aug 16, 2006 3:12 pm
by mamun
Thank you Darko for your nice long and clear explanation. :)

WA... somebody plz help me out!!

Posted: Sun Oct 14, 2007 9:48 am
by pradeepr
I dont know whts wrong with my code....
I followed exactly the same procedure as mentioned in the question..
can anyone please help me out...

Code: Select all

#include<iostream>
#include<string>
using namespace std;
void genpermute(string a, string b,int index)
{
        if(index==a.length())
        {
                cout<<b<<'\n';
        }
        else
        {
                string temp;
                string s(1,a[index]);
                for(int i=0;i<=index;i++)
                {
                        temp=b;
                        temp.insert(i,s);
                        genpermute(a,temp,index+1);
                }
        }
}
int main()
{
        string s;
        while(getline(cin,s))
        {
                if(s!="")
                {
                string temp="";

                genpermute(s,temp,0);
                }
                cout<<'\n';
        }
return(0);
}

Re: 10063 - Knuth's Permutation

Posted: Sun Apr 20, 2014 7:56 pm
by techbd123
Please help!
Why WA ?

Here's my code: https://ideone.com/9ZJysk

Re: 10063 - Knuth's Permutation

Posted: Mon Apr 21, 2014 11:27 pm
by brianfry713
Try running your code on the sample input.