string combination

[sophia]

Dear all,

The following is the program which i have done to find all the
combination of letters in the string "hello"

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

#define MAX 5

int main(void)
{
char t[MAX];
int i,j,k,l,m,n=1;

strcpy(t,"hello ");

printf("\n words formed from the combinations of all characters
from \
the word hello\n\n");

for(i = 0 ;i < MAX ;i++)
for(j = 0 ;j < MAX ;j++)
{
if(j == i)
continue;

for(k = 0 ;k < MAX ;k++)
{
if( (k==i) || (k == j) )
continue;

for(l = 0 ;l < MAX ;l++)
{

if( (l==i) || (l == j) || (l == k) )
continue;

m = 10 - (i + j + k + l);
printf("%c%c%c% c%c ",t[i],t[j],t[k],t[l],t[m]);

if(n %10 == 0) puts("");
n++;
}

}
}

printf("\n no: of words formed = %d",--n);

puts("");
return EXIT_SUCCESS;
}


can any one suggest a more general method so that i can find the
combination of letters of any inputted string ?

[Richard]

Re: string combination

sophia <sophia.agnes@g mail.comwrites:

Dear all,
>
The following is the program which i have done to find all the
combination of letters in the string "hello"
>
#include<stdio. h>
#include<stdlib .h>
#include<string .h>
>
#define MAX 5
>
int main(void)
{
char t[MAX];
int i,j,k,l,m,n=1;
>
strcpy(t,"hello ");
>
printf("\n words formed from the combinations of all characters
from \
the word hello\n\n");
>
for(i = 0 ;i < MAX ;i++)
for(j = 0 ;j < MAX ;j++)
{
if(j == i)
continue;
>
for(k = 0 ;k < MAX ;k++)
{
if( (k==i) || (k == j) )
continue;
>
for(l = 0 ;l < MAX ;l++)
{
>
if( (l==i) || (l == j) || (l == k) )
continue;
>
m = 10 - (i + j + k + l);
printf("%c%c%c% c%c ",t[i],t[j],t[k],t[l],t[m]);
>
if(n %10 == 0) puts("");
n++;
}
>
}
}
>
printf("\n no: of words formed = %d",--n);
>
puts("");
return EXIT_SUCCESS;
}
>
>
can any one suggest a more general method so that i can find the
combination of letters of any inputted string ?

For a start think about moving it all to another "non main" function
where you call it with the string you are interested in checking. This
"MAX" everywhere is horrible. Instead in your new function

displayAnagrams (char *s){
int len = strlen(s); /* or size_t ...... */
....
....
}

As for the algorithm itself, I have no idea.

Happy experimenting!

[santosh]

Re: string combination

sophia wrote:

Dear all,
>
The following is the program which i have done to find all the
combination of letters in the string "hello"
>
#include<stdio. h>
#include<stdlib .h>
#include<string .h>
>
#define MAX 5
>
int main(void)
{
char t[MAX];
int i,j,k,l,m,n=1;
>
strcpy(t,"hello ");
>
printf("\n words formed from the combinations of all characters
from \
the word hello\n\n");
>
for(i = 0 ;i < MAX ;i++)
for(j = 0 ;j < MAX ;j++)
{
if(j == i)
continue;
>
for(k = 0 ;k < MAX ;k++)
{
if( (k==i) || (k == j) )
continue;
>
for(l = 0 ;l < MAX ;l++)
{
>
if( (l==i) || (l == j) || (l == k) )
continue;
>
m = 10 - (i + j + k + l);
printf("%c%c%c% c%c ",t[i],t[j],t[k],t[l],t[m]);
>
if(n %10 == 0) puts("");
n++;
}
>
}
}
>
printf("\n no: of words formed = %d",--n);
>
puts("");
return EXIT_SUCCESS;
}
>
>
can any one suggest a more general method so that i can find the
combination of letters of any inputted string ?

<http://www.theory.csc. uvic.ca/~cos/inf/perm/PermInfo.html>
<http://c.snippets.org/snip_lister.php ?fname=permute2 .c>
<http://mathworld.wolfr am.com/Permutation.htm l>
<http://regentsprep.org/Regents/Math/permut/Lperm.htm>

[vippstar@gmail.com]

Re: string combination

On Apr 15, 6:17 pm, sophia <sophia.ag...@g mail.comwrote:

Dear all,
>
The following is the program which i have done to find all the
combination of letters in the string "hello"
>
#include<stdio. h>
#include<stdlib .h>
#include<string .h>
>
#define MAX 5
>
int main(void)
{
char t[MAX];
int i,j,k,l,m,n=1;
>
strcpy(t,"hello ");

t is char[MAX], char[5]. "hello" consists of 6 elements, so change
that.
Search on google about combinations and code. (which are not directly
related to C)

[Bartc]

Re: string combination

sophia wrote:

Dear all,
>
The following is the program which i have done to find all the
combination of letters in the string "hello"

....

>
can any one suggest a more general method so that i can find the
combination of letters of any inputted string ?

The following code (showpermutatio ns()) displays all permutations of the
characters in any string.

But: it does not deal with repeated characters (so perms of aaa would be
aaa,aaa,aaa,aaa ,aaa,aaa). And capturing the output is tricky; here it justs
prints the results. And, I suspect there's a much more elegant way to do
this..

I've built-in a maximum word length of 99 characters; however such a word
would print 99! lines of output.

Maybe this helps.

/* Display all permutations of characters in a word. Ignores duplicate chars
*/

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

void showpermutation s(char *prefix, char *word);

#define maxwordlen 100

int main(void) {
showpermutation s("","abcd");
}

void showpermutation s(char *prefix, char *word) {
char newprefix[maxwordlen];
char newword[maxwordlen];
char c[2]={0,0};
char d[2]={0,0};
int i,j,len;

if (prefix==NULL || word==NULL) return;

len=strlen(word );

if (len<=1) {
printf("%s%s\n" ,prefix,word);
return;
};

for(i=0; i<len; ++i) {
c[0]=word[i];
newword[0]=0;

for (j=0; j<len; ++j)
if (j!=i) {
d[0]=word[j];
strcat(newword, d);
};

strcpy(newprefi x,prefix);
strcat(newprefi x,c);
showpermutation s(newprefix,new word);
};

}



--
Bart

[Willem]

Re: string combination

sophia wrote:
) Dear all,
)
) The following is the program which i have done to find all the
) combination of letters in the string "hello"
)
) <snip>
)
) can any one suggest a more general method so that i can find the
) combination of letters of any inputted string ?

To print all permutations of a string, you have to print each of its
characters as a first character, and then print all the permutations
of the remaining characters.

One way to get 'each of the characters' and 'the remaining characters'
is to rotate the string in-place so that each character is put
at the front in turn.

Given this, here's a recursive solution:

void rotate(char *ptr, int len)
{
char tmp = *ptr;
memmove(ptr, ptr+1, len-1);
ptr[len-1] = tmp;
}

void recurse_perms(c har *str, char *ptr, int len)
{
int i;
if (len) {
for (i = 0; i < len; i++) {
recurse_perms(s tr, ptr+1, len-1);
rotate(ptr, len);
}
} else {
printf("%s\n", str);
}
}

void print_perms(cha r *str)
{
/* NB: If str can be const, make a copy here */
recurse_perms(s tr, str, strlen(str));
}


If you want more performance, you can also use a swap operation
instead of a rotate, but then it's a bit harder to figure out exactly
what to swap to where.

Note that the recursive function returns the substring at *ptr
to its original state. This is needed for the function to work.
(And that's why swapping is a lot harder conceptually.)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[user923005]

Re: string combination

On Apr 15, 8:17 am, sophia <sophia.ag...@g mail.comwrote:

Dear all,
>
The following is the program which i have done to find all the
combination of letters in the string "hello"
>
 #include<stdio. h>
 #include<stdlib .h>
 #include<string .h>
>
 #define MAX 5
>
 int main(void)
 {
   char t[MAX];
   int  i,j,k,l,m,n=1;
>
   strcpy(t,"hello ");
>
   printf("\n words formed from the combinations of all characters
from \
   the  word hello\n\n");
>
   for(i = 0 ;i < MAX ;i++)
   for(j = 0 ;j < MAX ;j++)
   {
      if(j == i)
      continue;
>
          for(k = 0 ;k < MAX ;k++)
          {
            if( (k==i) || (k == j) )
            continue;
>
            for(l = 0 ;l < MAX ;l++)
                {
>
                  if( (l==i) || (l == j) || (l == k) )
          continue;
>
          m = 10 - (i + j + k + l);
          printf("%c%c%c% c%c ",t[i],t[j],t[k],t[l],t[m]);
>
                  if(n %10 == 0) puts("");
          n++;
            }
>
          }
   }
>
   printf("\n no: of words formed = %d",--n);
>
   puts("");
   return EXIT_SUCCESS;
 }
>
can any one suggest a more general method so that i can find the
combination of letters of any inputted string ?

This is a modification of an IOCCC entry:

E:\dict>foo.bat hellosophia

E:\dict>anagram -1 hellosophia 0<big.dict 1>hellosophia

E:\dict>anagram -2 hellosophia 0<big.dict 1>>hellosophia

E:\dict>anagram -3 hellosophia 0<big.dict 1>>hellosophia

E:\dict>anagram -4 hellosophia 0<big.dict 1>>hellosophia
E:\dict>type foo.bat
anagram -1 %1 < big.dict %1
anagram -2 %1 < big.dict >>%1
anagram -3 %1 < big.dict >>%1
anagram -4 %1 < big.dict >>%1

E:\dict>type anagram.c
#include <stdio.h>
#include <stdlib.h>
#include <io.h>
#include <string.h>

char *getsafe(char *buffer, int count)
{
char *result = buffer,
*np;
if ((buffer == NULL) || (count < 1))
result = NULL;
else if (count == 1)
*result = '\0';
else if ((result = fgets(buffer, count, stdin)) != NULL)
if (np = strchr(buffer, '\n'))
*np = '\0';
return result;
}


static long a[4],
b[4],
c[4],
d[0400],
e = 1;

typedef struct f {
long g,
h,
i[4],
j;
struct f *k;
} f;

extern long n(long *o, long *p, long *q);
extern void t(int i, long *p);
extern int u(struct f * j);
extern int v(struct f * j, int s);
extern int w(struct f * o, int r, struct f * j, int x, long p);
extern int y(void);
extern int main(int o, char **p);

static f g,
*l[4096];

static char h[256],
*m,
k = 3;

long n(long *o, long *p, long *q)
{
long r = 4,
s,
i = 0;
for (; r--; s = i ^ *o ^ *p, i = i & *p | (i | *p) & ~*o++, *q++ =
s, p++);
return i;
}

void t(int i, long *p)
{
*c = d[i], n(a, c, b), n(p, b, p);
}
int u(struct f * j)
{
j->h = (j->g = j->i[0] | j->i[1] | j->i[2] | j->i[3]) & 4095;
return 0;
}
int v(struct f * j, int s)
{
int i;
for (j->k->k && v(j->k, ' '), fseek(stdin, j->j, 0); i =
getchar(), putchar(i - '\n' ? i : s), i - '\n';);
return 0;
}
int w(struct f * o, int r, struct f * j, int x, long p)
{
f q;
int
s,
i = o->h;
q.k = o;
r i ? j = l[r = i] : r < i && (s = r & ~i) ? (s |= s >1, s |=
s >2, s |= s >4, s |= s >8, j = l[r = ((r & i | s) & ~(s >1))
- 1 & i]) : 0;
--x;
for (; x && !(p & i); p >>= 1);
for (; !x && j; n(o->i, j->i, q.i), u(&q), q.g || (q.j = j->j,
v(&q, '\n')), j = j->k);
for (; x; j = x ? j->k : 0) {
for (; !j && ((r = (r & i) - 1 & i) - i && (r & p) ? 2 : (x =
0)); j = l[r]);
!x || (j->g & ~o->g) || n(o->i, j->i, q.i) || (u(&q), q.j = j-

>j, q.g ? w(&q, r, j->k, x, p) : v(&q, '\n'));

}
return 0;
}
int y(void)
{
f
j;
char *z,
*p;
for (; m ? j.j = ftell(stdin), 7, (m = getsafe(m, sizeof h)) ||
w(&g, 315 * 13, l[4095], k, 64 * 64) & 0 : 0; n(g.i, j.i, b) ||
(u(&j), j.k = l[j.h], l[j.h] = &j, y())) {
for (z = p = h; *z && (d[*z++] || (p = 0)););
for (z = p ? n(j.i, j.i, j.i) + h : ""; *z; t(*z++, j.i));
}
return 0;
}
int main(int o, char **p)
{
for (; m = *++p;)
for (; *m - '-' ? *m : (k = -atoi(m)) & 0; d[*m] || (d[*m] =
e, e <<= 1), t(*m++, g.i));
u(&g), m = h, y();
return 0;
}

E:\dict>type hellosophia|mor e
opalish hole
pasillo hohe
pasillo heho
sophia holle
sophia hello
pliÈ ooh
pliÈ oho
pliÈ hoo
pallies hoho
pailles hoho
illapse hoho
silpha ohelo
phlias ohelo
phials ohelo
palish ohelo
saphie hollo
philohela so
philohela os
ophelia losh
ophelia hols
liaopeh losh
liaopeh hols
halophile so
halophile os
lophiola she
lophiola hes
lophiola esh
lophiola ehs
pohai hellos
ophia hellos
philae shool
phiale shool
phelia shool
phalli hoose
phia holloes
pahi holloes
hapi holloes
hilloas peho
hilloas hope
sheilah pool
sheilah polo
sheilah oopl
sheilah loop
elishah pool
elishah polo
elishah oopl
elishah loop
shilha poole
shilha loope
lisha hoople
hilsah poole
hilsah loope
hilsa hoople
hails hoople
ashli hoople
ashil hoople
alish hoople
aiello phohs
holia hoples
hilloa shope
hilloa phose
hilloa hopes
leilah shoop
leilah posho
leilah poohs
leilah hoops
helali shoop
helali posho
helali poohs
helali hoops
hallie shoop
hallie posho
hallie poohs
hallie hoops
lilah hoopes
hilla hoopes
halli hoopes
polash helio
pholas helio
hooplas lehi
hooplas hile
hooplas heli
hooplas heil
hooplas elhi
alphos helio
shapoo hilel
shapoo helli
pasho hollie
pahos hollie
opahs hollie
plash hoolie
shap oilhole
psha oilhole
pash oilhole
pahs oilhole
^C
E:\dict>

[sophia]

Re: string combination

On Apr 15, 3:46 pm, user923005 <dcor...@connx. comwrote:

E:\dict>type anagram.c
#include <stdio.h>
#include <stdlib.h>
#include <io.h>

but <io.his a non standard , non ANSI header file is n't it ?


E:\dict>type hellosophia|mor e

I think this should be rather E:\dict>anagram hellosophia|mor e

[Richard Heathfield]

Re: string combination

sophia said:

On Apr 15, 3:46 pm, user923005 <dcor...@connx. comwrote:
>

>E:\dict>type anagram.c
>#include <stdio.h>
>#include <stdlib.h>
>#include <io.h>

>
but <io.his a non standard , non ANSI header file is n't it ?

Yes. You caught him.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Bartc]

Re: string combination


"sophia" <sophia.agnes@g mail.comwrote in message
news:f82c66ad-4725-4be6-8a68-2c09a11fafdd@q1 0g2000prf.googl egroups.com...

On Apr 15, 3:46 pm, user923005 <dcor...@connx. comwrote:
>

>E:\dict>type anagram.c
>#include <stdio.h>
>#include <stdlib.h>
>#include <io.h>

>
but <io.his a non standard , non ANSI header file is n't it ?
>
>
E:\dict>type hellosophia|mor e
>
I think this should be rather E:\dict>anagram hellosophia|mor e

It also generates anagrams of course rather than just all the combinations
of the letters.

It could also have done with small.dict rather than big.dict.

-- Bartc

[CBFalconer]

Re: string combination

Bartc wrote:

>

.... snip ...

>
It also generates anagrams of course rather than just all the
combinations of the letters.
>
It could also have done with small.dict rather than big.dict.

This generates full anagrams.

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

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

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

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

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

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.


** Posted from http://www.teranews.com **

[user923005]

Re: string combination

On Apr 16, 2:49 am, "Bartc" <b...@freeuk.co mwrote:

"sophia" <sophia.ag...@g mail.comwrote in message
>
news:f82c66ad-4725-4be6-8a68-2c09a11fafdd@q1 0g2000prf.googl egroups.com...
>

On Apr 15, 3:46 pm, user923005 <dcor...@connx. comwrote:

>

E:\dict>type anagram.c
#include <stdio.h>
#include <stdlib.h>
#include <io.h>

>

but <io.his a non standard , non ANSI header file is n't it ?

>

E:\dict>type hellosophia|mor e

>

I think this should be rather E:\dict>anagram hellosophia|mor e

>
It also generates anagrams of course rather than just all the combinations
of the letters.

In the original post, the output line said "words formed" which is why
I chose anagram rather than permutation.

It could also have done with small.dict rather than big.dict.

So size doesn't matter?

[jaysome]

Re: string combination

On Wed, 16 Apr 2008 09:13:08 -0400, CBFalconer <cbfalconer@yah oo.com>
wrote:

>Bartc wrote:

>>

>... snip ...

>>
>It also generates anagrams of course rather than just all the
>combinations of the letters.
>>
>It could also have done with small.dict rather than big.dict.

>
>This generates full anagrams.

jumble support@aol.com

This outputs lines of text indefinitely.

Is that a bug or a feature?

--
jay

[Eric Sosman]

Re: string combination

jaysome wrote:

On Wed, 16 Apr 2008 09:13:08 -0400, CBFalconer <cbfalconer@yah oo.com>
wrote:
>

>Bartc wrote:
>... snip ...

>>It also generates anagrams of course rather than just all the
>>combination s of the letters.
>>>
>>It could also have done with small.dict rather than big.dict.

>This generates full anagrams.

>
jumble support@aol.com
>
This outputs lines of text indefinitely.

You didn't wait long enough. The code was posted just
yesterday, and even if your computer can spit out a million
lines a second it will take more than two weeks to finish.

Is that a bug or a feature?

Feature. Fifteen factorial is >1.3e12.

--
Eric.Sosman@sun .com

[CBFalconer]

Re: string combination

jaysome wrote:

CBFalconer <cbfalconer@yah oo.comwrote:

>Bartc wrote:

>>>

>>... snip ...

>>>
>>It also generates anagrams of course rather than just all the
>>combination s of the letters.
>>>
>>It could also have done with small.dict rather than big.dict.

>>
>This generates full anagrams.

>
jumble support@aol.com
>
This outputs lines of text indefinitely.
>
Is that a bug or a feature?

You want all anagrams of a 15 char word? That will take a while.
It will generate about 1.3e12 words. That is 1.3 million million
words!

Try it on shorter words, or limit the output length. e.g: "jumble
gupp" and "jumble gupp 3". Also try redirecting output to a file
so you can read the initial line to stderr.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.


** Posted from http://www.teranews.com **