Permutations of a String
Kiran Dalvi
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
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?
CBFalconer
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
% 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
Ben Pfaff
> rayoflig...@yahoo.com (Kiran Dalvi) wrote in message news:<b33f94a.04040...@posting.google.com>...
>> 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
Vijay Kumar R Zanvar
"Kiran Dalvi" <rayoflig...@yahoo.com> wrote in message news:b33f94a.04040...@posting.google.com...
#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
> 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)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.
>
> 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