10063 - Knuth's Permutation

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10063 - Knuth's Permutation

Post by stcheung » Tue Dec 10, 2002 2:22 pm

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]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Dec 14, 2002 12:47 pm

Simple changes can be made to accomodate a string with size 0... =)

your >> skips right over it.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10063 Knuth's Permutation again

Post by stcheung » Mon Jan 13, 2003 1:20 pm

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]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

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

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:

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Tue Mar 11, 2003 11:23 am

Thanks red scorpion, I know this rule now, and my solution before is WA. :oops:

oXy
New poster
Posts: 2
Joined: Sun Apr 06, 2003 9:53 am

10063

Post by oXy » Sun Apr 06, 2003 11:59 am

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]
Stefan

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Tue Apr 08, 2003 5:10 pm

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:

oXy
New poster
Posts: 2
Joined: Sun Apr 06, 2003 9:53 am

Post by oXy » Thu Apr 10, 2003 3:28 pm

10x, i got AC now.

But I still can't tell what the difference between

while (gets(str))
{
}

and

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

is.
Stefan

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Apr 29, 2003 9:34 pm

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Fri Dec 02, 2005 8:39 am

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jul 28, 2006 3:03 am

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>

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Wed Aug 16, 2006 3:12 pm

Thank you Darko for your nice long and clear explanation. :)

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

WA... somebody plz help me out!!

Post by pradeepr » Sun Oct 14, 2007 9:48 am

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

techbd123
New poster
Posts: 14
Joined: Tue Aug 06, 2013 3:42 pm

Re: 10063 - Knuth's Permutation

Post by techbd123 » Sun Apr 20, 2014 7:56 pm

Please help!
Why WA ?

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

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

Re: 10063 - Knuth's Permutation

Post by brianfry713 » Mon Apr 21, 2014 11:27 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”