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 7 4449
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
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> 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 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
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
"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;
}
"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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Steve Goldman |
last post by:
Hi,
I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can't
help thinking there's a better way. ...
|
by: Jeff Kish |
last post by:
Hi.
I realize this might be more of a "figure out the algorithm" thing than
strictly an std question.. sorry if it is off topic? It certainly was in the
other group!
Also, I'm pretty old, not...
|
by: Kiran Dalvi |
last post by:
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,...
|
by: Girish Sahani |
last post by:
Hi guys,
I want to generate all permutations of a string. I've managed to
generate all cyclic permutations. Please help :)
def permute(string):
l=
l.append(string)
string1 = ''
for i in...
|
by: anurag |
last post by:
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
| |
by: Christian Meesters |
last post by:
Hi,
I'd like to hack a function which returns all possible permutations as lists
(or tuples) of two from a given list. So far, I came up with this solution,
but it turned out to be too slow for...
|
by: JosAH |
last post by:
Greetings,
last week I stated that a lot of topics in a lot of forums mention all sorts
of sorting problems. Last week's tip gave an answer to quite a bit of those
sorting problems. Another...
|
by: JosAH |
last post by:
Greetings,
last week we talked a bit about generating permutations and I told you that
this week will be about combinations. Not true; there's a bit more to tell
about permutations and that's...
|
by: Shraddha |
last post by:
Suppose we are having 3 variables...a,b,c
And we want to print the permutations of these variables...Such
as...abc,acb,bca...all 6 of them...
But we are not supposed to do it mannually...
I...
|
by: Assimalyst |
last post by:
Hi
I have a Dictionary<string, List<string>>, which i have successfully
filled. My problem is I need to create a filter expression using all
possible permutations of its contents.
i.e. the...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
| |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |