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]

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?

--
Er*********@sun.com

[CBFalconer]

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

ra**************@yahoo.com (Kiran Dalvi) wrote in message news:<b3*************************@posting.google.c om>...

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)re turn 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

[Ben Pfaff]

ai***@acay.com.au (Peter Nilsson) writes:

ra**************@yahoo.com (Kiran Dalvi) wrote in message news:<b3*************************@posting.google.c om>...

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)re turn 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

[Arthur J. O'Dwyer]

On Tue, 6 Apr 2004, Ben Pfaff wrote:

ai***@acay.com.au (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)re turn 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

[Vijay Kumar R Zanvar]

"Kiran Dalvi" <ra**************@yahoo.com> wrote in message news:b3*************************@posting.google.co m...

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

[Hegemony Cricket]

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message news:<Pi***********************************@unix44 .andrew.cmu.edu>...

On Tue, 6 Apr 2004, Ben Pfaff wrote:

ai***@acay.com.au (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)re turn 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