Permutations of a String

[Kiran Dalvi]

Hi,
Can anybody please suggest me an efficient approach to find out all
possible permutations of a String.
e.g. My input string = "ABC".
My program should give an output like ....
ABC, ACB, BAC, BCA, CAB, CBA

Thanks,
Kiran

[Eric Sosman]

Re: Permutations of a String

Kiran Dalvi wrote:[color=blue]
>
> Hi,
> Can anybody please suggest me an efficient approach to find out all
> possible permutations of a String.
> e.g. My input string = "ABC".
> My program should give an output like ....
> ABC, ACB, BAC, BCA, CAB, CBA[/color]

There are at least two things wrong with your question:

- It's not about the C language, but about an algorithm.

- It stinks to high heaven of homework.

That said, here's a solution:

#include <stdio.h>
#include <string.h>
int main(int argc, char **argv) {
return !!printf(strcmp (argc==2?*++arg v:"ABC\n"),"ABC ")?
"I can't do that, Dave\n":"ABC, ACB, BAC, BCA, CAB, CBA\n"));
}

It might be possible to improve on this solution. One
avenue of exploration would be to consider the principle of
mathematical induction: You probably know how to generate
all the permutations of a one-letter string. Now if you
have a method for permuting N-letter strings, can you think
of a way to generate all the permutations of (N+1)-letter
strings?

--
Eric.Sosman@sun .com

[CBFalconer]

Re: Permutations of a String

Kiran Dalvi wrote:[color=blue]
>
> Can anybody please suggest me an efficient approach to find out
> all possible permutations of a String.
> e.g. My input string = "ABC".
> My program should give an output like ....
> ABC, ACB, BAC, BCA, CAB, CBA[/color]

I just happen to have this lying about. Works nicely in
conjunction with the following 4dos alias:

c:\c\jumble>ali as jumble
\c\jumble\jumbl e %1& | sort | uniq | pr -a -T --columns=8

*** No two chars are the same in the following string ***
c:\c\jumble>jum ble 0O1l
string="0O1l", max=24, len=4
01Ol 01lO 0O1l 0Ol1 0l1O 0lO1 10Ol 10lO
1O0l 1Ol0 1l0O 1lO0 O01l O0l1 O10l O1l0
Ol01 Ol10 l01O l0O1 l10O l1O0 lO01 lO10


------------- cut for file jumble.c ------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd[i];
wd[i] = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring) ;
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"% s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

--
Some useful references:
<http://www.ungerhu.com/jxh/clc.welcome.txt >
<http://www.eskimo.com/~scs/C-faq/top.html>
<http://benpfaff.org/writings/clc/off-topic.html>

[Peter Nilsson]

Re: Permutations of a String

rayoflight_kira n@yahoo.com (Kiran Dalvi) wrote in message news:<b33f94a.0 404060631.5bf69 023@posting.goo gle.com>...[color=blue]
> Hi,
> Can anybody please suggest me an efficient approach to find out all
> possible permutations of a String.
> e.g. My input string = "ABC".
> My program should give an output like ....
> ABC, ACB, BAC, BCA, CAB, CBA[/color]

% type perm2.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void q1(char*q2,char *q3)??<char q4=*q2;*q2=*q3; *q3=q4;??>void q5(
char*q2,char*q3 )??<if(q2!=q3)f or(;q2<--q3;q2++)q1(q2,q 3);??>int
q6(char*q2,char *q3)??<char*q7, *q8,*q9;if(q2== q3)return 0;for(q7=
q3-1;q2<q7;)??<q8= q7--;if(*q7<*q8)??< q9=q3;while(*q7 >=*--q9);q1(
q7,q9);q5(q8,q3 );return 1;??>??>q5(q2,q 3);return 0;??>int q10(
const void*q2,const void*q3)??<cons t char*q11=q2,*q1 2=q3;return(
*q11>*q12)-(*q11<*q12);??> int main(int q13,char*q14[])??<size_t
q15;if(q13!=2)r eturn 0;q15=strlen(q1 4[1]);qsort(q14[1],q15,1,q10
);do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

% acc perm2.c -o perm.exe
perm2.c: warning: 14 trigraph(s) encountered

% perm ABC
ABC
ACB
BAC
BCA
CAB
CBA

% perm 1100
0011
0101
0110
1001
1010
1100

%

--
Peter

[Ben Pfaff]

Re: Permutations of a String

airia@acay.com. au (Peter Nilsson) writes:
[color=blue]
> rayoflight_kira n@yahoo.com (Kiran Dalvi) wrote in message news:<b33f94a.0 404060631.5bf69 023@posting.goo gle.com>...[color=green]
>> Hi,
>> Can anybody please suggest me an efficient approach to find out all
>> possible permutations of a String.
>> e.g. My input string = "ABC".
>> My program should give an output like ....
>> ABC, ACB, BAC, BCA, CAB, CBA[/color]
>
> % type perm2.c
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> void q1(char*q2,char *q3)??<char q4=*q2;*q2=*q3; *q3=q4;??>void q5(
> char*q2,char*q3 )??<if(q2!=q3)f or(;q2<--q3;q2++)q1(q2,q 3);??>int
> q6(char*q2,char *q3)??<char*q7, *q8,*q9;if(q2== q3)return 0;for(q7=
> q3-1;q2<q7;)??<q8= q7--;if(*q7<*q8)??< q9=q3;while(*q7 >=*--q9);q1(
> q7,q9);q5(q8,q3 );return 1;??>??>q5(q2,q 3);return 0;??>int q10(
> const void*q2,const void*q3)??<cons t char*q11=q2,*q1 2=q3;return(
> *q11>*q12)-(*q11<*q12);??> int main(int q13,char*q14[])??<size_t
> q15;if(q13!=2)r eturn 0;q15=strlen(q1 4[1]);qsort(q14[1],q15,1,q10
> );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>[/color]

This would be more impressive if I could permute the lines in the
program into any order and it would still perform correctly.
Actually, that's a great idea for an IOCCC entry.
--
"...deficie nt support can be a virtue.
It keeps the amateurs off."
--Bjarne Stroustrup

[Arthur J. O'Dwyer]

Line-permutable, was re: Permutations of a String


On Tue, 6 Apr 2004, Ben Pfaff wrote:[color=blue]
>
> airia@acay.com. au (Peter Nilsson) writes:[color=green]
> >
> > % type perm2.c
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> >
> > void q1(char*q2,char *q3)??<char q4=*q2;*q2=*q3; *q3=q4;??>void q5(
> > char*q2,char*q3 )??<if(q2!=q3)f or(;q2<--q3;q2++)q1(q2,q 3);??>int
> > q6(char*q2,char *q3)??<char*q7, *q8,*q9;if(q2== q3)return 0;for(q7=
> > q3-1;q2<q7;)??<q8= q7--;if(*q7<*q8)??< q9=q3;while(*q7 >=*--q9);q1(
> > q7,q9);q5(q8,q3 );return 1;??>??>q5(q2,q 3);return 0;??>int q10(
> > const void*q2,const void*q3)??<cons t char*q11=q2,*q1 2=q3;return(
> > *q11>*q12)-(*q11<*q12);??> int main(int q13,char*q14[])??<size_t
> > q15;if(q13!=2)r eturn 0;q15=strlen(q1 4[1]);qsort(q14[1],q15,1,q10
> > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>[/color]
>
> This would be more impressive if I could permute the lines in the
> program into any order and it would still perform correctly.
> Actually, that's a great idea for an IOCCC entry.[/color]

*Really* great! I'll admit it's late and I'm unusually sleepy,
but I can't even come up with a single example of a non-trivially
line-permutable program, let alone a non-trivial program that is
also line-permutable! I mean, not counting

int main() { puts("foo"); return 0; }
int i;

and the like, I can't see any way to construct a line-permutable C
program at all. Something with line-continuations (\), maybe, where
'int main' on one line magically turns into 'fooint main' when it's
permuted before a line ending in 'foo\'. That sort of thing.
Mad props will go to the first non-trivially permutable program to
be posted. :)

-Arthur

[Vijay Kumar R Zanvar]

Re: Permutations of a String


"Kiran Dalvi" <rayoflight_kir an@yahoo.com> wrote in message news:b33f94a.04 04060631.5bf690 23@posting.goog le.com...[color=blue]
> Hi,
> Can anybody please suggest me an efficient approach to find out all
> possible permutations of a String.
> e.g. My input string = "ABC".
> My program should give an output like ....
> ABC, ACB, BAC, BCA, CAB, CBA
>
> Thanks,
> Kiran[/color]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void
string_combi ( char * s, int len )
{
int i;
char tmp;
static int j;
static char *p;

if ( !p )
p = s;

for ( i = 1; i <= len; i++ )
{
if ( len > 2 )
string_combi ( s+1, len-1 );
else
{
j++;
printf ( "%d: %s\t", j, p );
if ( !( j%10 ) )
puts ( "" );
}
if ( i < len )
{
tmp = s[len-i];
s[len-i] = s[0];
s[0] = tmp;
}
}
return;
}

int
main()
{
char s[50];

printf("\n Enter String : ");
scanf("%s%*c", s);
string_combi ( s, strlen ( s ) );

return EXIT_SUCCESS;
}

[Hegemony Cricket]

Re: Line-permutable, was re: Permutations of a String

"Arthur J. O'Dwyer" <ajo@nospam.and rew.cmu.edu> wrote in message news:<Pine.LNX. 4.58-035.04040701225 10.21107@unix44 .andrew.cmu.edu >...[color=blue]
> On Tue, 6 Apr 2004, Ben Pfaff wrote:[color=green]
> >
> > airia@acay.com. au (Peter Nilsson) writes:[color=darkred]
> > >
> > > % type perm2.c
> > > #include <stdio.h>
> > > #include <stdlib.h>
> > > #include <string.h>
> > >
> > > void q1(char*q2,char *q3)??<char q4=*q2;*q2=*q3; *q3=q4;??>void q5(
> > > char*q2,char*q3 )??<if(q2!=q3)f or(;q2<--q3;q2++)q1(q2,q 3);??>int
> > > q6(char*q2,char *q3)??<char*q7, *q8,*q9;if(q2== q3)return 0;for(q7=
> > > q3-1;q2<q7;)??<q8= q7--;if(*q7<*q8)??< q9=q3;while(*q7 >=*--q9);q1(
> > > q7,q9);q5(q8,q3 );return 1;??>??>q5(q2,q 3);return 0;??>int q10(
> > > const void*q2,const void*q3)??<cons t char*q11=q2,*q1 2=q3;return(
> > > *q11>*q12)-(*q11<*q12);??> int main(int q13,char*q14[])??<size_t
> > > q15;if(q13!=2)r eturn 0;q15=strlen(q1 4[1]);qsort(q14[1],q15,1,q10
> > > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>[/color]
> >
> > This would be more impressive if I could permute the lines in the
> > program into any order and it would still perform correctly.
> > Actually, that's a great idea for an IOCCC entry.[/color]
>
> *Really* great! I'll admit it's late and I'm unusually sleepy,
> but I can't even come up with a single example of a non-trivially
> line-permutable program, let alone a non-trivial program that is
> also line-permutable![/color]
[...][color=blue]
> Mad props will go to the first non-trivially permutable program to
> be posted. :)[/color]


Uh, dudes? One of last year's winners did this, and marvelously too.
Go to http://www.ioccc.org and under "Winning entries" for 2001, look
for "westley"'s .


--Mark