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

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

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,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.wolfram.com/Permutation.html>
<http://regentsprep.org/Regents/Math/permut/Lperm.htm>

 

[vippstar]

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]

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 (showpermutations()) 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 showpermutations(char *prefix, char *word);

#define maxwordlen 100

int main(void) {
showpermutations("","abcd");
}

void showpermutations(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;
newword[0]=0;

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

strcpy(newprefix,prefix);
strcat(newprefix,c);
showpermutations(newprefix,newword);
};

}

 

[Willem]

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(char *str, char *ptr, int len)
{
int i;
if (len) {
for (i = 0; i < len; i++) {
recurse_perms(str, ptr+1, len-1);
rotate(ptr, len);
}
} else {
printf("%s\n", str);
}
}

void print_perms(char *str)
{
/* NB: If str can be const, make a copy here */
recurse_perms(str, 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]

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,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, 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|more
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]

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

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


E:\dict>type hellosophia|more

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

 

[Bartc]

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


E:\dict>type hellosophia|more

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

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

 

[user923005]

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]

This generates full anagrams.

jumble (e-mail address removed)

This outputs lines of text indefinitely.

Is that a bug or a feature?

 

[jaysome]

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.

I feel like an idiot. Your program deals with anagrams, but somehow I
thought it dealt with palindromes. My bad.

Sorry,

 

[Bartc]

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!

That would be permutations of all the letters.

I thought anagrams would be all words and phrases that could be made from
the letters, with each word being meaningful.

For that it would need input in the form of a dictionary.

And I don't think the combinations would be anything like 1.3 trillion.
(Unless you allow each letter of the alphabet to be a word, but then the
combinations I /think/ might be more than 15! because of introducing up to
14 spaces into the results)

 

[Bartc]

Then you haven't look at the program. Here are a couple of aliases
that I use to cut the output down to something usable:

I've looked at it briefly. But I've run it. And it produces permutations!

I doubt whether passing the output through all those filters can produce
true multi-word anagrams (although I don't know what comm does; I have a
feeling it chooses only those words in a dictionary, in that case yes it
would generate single-word anagrams)

BTW your usage message assumes the program is called 'jumble'.

 

[santosh]

CBFalconer wrote:

sort, uniq, comm, pr are standard Unix or Linux programs, and are
also available on Winders under djgpp.

<snip>

Another option is:

<http://unxutils.sourceforge.net/>