# Permutations of a String

Discussion in 'C Programming' started by Kiran Dalvi, Apr 6, 2004.

1. ### Kiran DalviGuest

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

Kiran Dalvi, Apr 6, 2004

2. ### Eric SosmanGuest

Kiran Dalvi wrote:
>
> 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

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?*++argv:"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, Apr 6, 2004

3. ### CBFalconerGuest

Kiran Dalvi wrote:
>
> 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

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

c:\c\jumble>alias jumble
\c\jumble\jumble %1& | sort | uniq | pr -a -T --columns=8

*** No two chars are the same in the following string ***
c:\c\jumble>jumble 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;
wd = 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>

CBFalconer, Apr 6, 2004
4. ### Peter NilssonGuest

(Kiran Dalvi) wrote in message news:<>...
> 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

% 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)for(;q2<--q3;q2++)q1(q2,q3);??>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,q3);return 0;??>int q10(
const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
*q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
q15;if(q13!=2)return 0;q15=strlen(q14[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

Peter Nilsson, Apr 7, 2004
5. ### Ben PfaffGuest

(Peter Nilsson) writes:

> (Kiran Dalvi) wrote in message news:<>...
>> 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

>
> % 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)for(;q2<--q3;q2++)q1(q2,q3);??>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,q3);return 0;??>int q10(
> const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
> *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
> q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
> );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

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.
--
"...deficient support can be a virtue.
It keeps the amateurs off."
--Bjarne Stroustrup

Ben Pfaff, Apr 7, 2004
6. ### Arthur J. O'DwyerGuest

Line-permutable, was re: Permutations of a String

On Tue, 6 Apr 2004, Ben Pfaff wrote:
>
> (Peter Nilsson) writes:
> >
> > % 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)for(;q2<--q3;q2++)q1(q2,q3);??>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,q3);return 0;??>int q10(
> > const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
> > *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
> > q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
> > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

>
> 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.

*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

Arthur J. O'Dwyer, Apr 7, 2004
7. ### Vijay Kumar R ZanvarGuest

"Kiran Dalvi" <> wrote in message news:...
> 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

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

Vijay Kumar R Zanvar, Apr 7, 2004
8. ### Hegemony CricketGuest

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

"Arthur J. O'Dwyer" <> wrote in message news:<>...
> On Tue, 6 Apr 2004, Ben Pfaff wrote:
> >
> > (Peter Nilsson) writes:
> > >
> > > % 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)for(;q2<--q3;q2++)q1(q2,q3);??>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,q3);return 0;??>int q10(
> > > const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
> > > *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
> > > q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
> > > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

> >
> > 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.

>
> *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!

[...]
> Mad props will go to the first non-trivially permutable program to
> be posted.

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

Hegemony Cricket, Apr 12, 2004

### Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.