anurag said:

1) All the strings starting with A and continuing with some permutation of
BCD
2) All the strings starting with B and continuing with some permutation of
CDA
3) All the strings starting with C and continuing with some permutation of
DAB
4) All the strings starting with D and continuing with some permutation of
ABC

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with A and continuing with some
permutation of BCD.

We are now faced with the problem of finding all the strings containing BCD
(which we can simply append to A to get the full permutation).

We can think of the permutations of this string as being divided into three
sets (because the string is three characters long):

1) All the strings starting with B and continuing with some permutation of
CD
2) All the strings starting with C and continuing with some permutation of
DB
3) All the strings starting with D and continuing with some permutation of
BC

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then) B and
continuing with some permutation of CD.

We are now faced with the problem of finding all the strings containing CD
(which we can simply append to AB to get the full permutation).

We can think of the permutations of this string as being divided into two
sets (because the string is two characters long):

1) All the strings starting with C and continuing with some permutation of D
2) All the strings starting with D and continuing with some permutation of C

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then B and then) C,
and continuing with some permutation of D.

We are now faced with the problem of finding all the strings containing D
(which we can simply append to ABC to get the full permutation).

We can think of the permutations of this string as being divided into one
set (because the string is one character long):

1) All the string starting with D - which is obvious, of course.

The canonical way to do this is via recursion, passing in the string,
together with the number of items yet to be permuted. If that number is 0,
simply display the string. Otherwise, loop around the leftmost
not-yet-handled character and, within the loop, recurse with n-1.

Now take a crack at it yourself, and let us know how you get on.

In any case, to give a concrete example of what R.H. discusses
elsethread, here's an attempt I made a few weeks ago, when the question
first came up. Take it as you will.

For the regulars: yes I know that answering a homework question is
frowned apon, and even worse is answering an algorithm question, but
this one piqued my interest. So, for my one freebie a year, I post this
code   ;-)

==snip==

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

void rotate(unsigned length, char *string)
{
  char save;

  save = *string;
  while(--length)
  {
    *string=*(string+1);
    ++string;
  }
  *string = save;

  if (length == 0)
    printf("%s\n",string-depth);
  else
  {
    unsigned count;

    for (count = length ; count > 0; --count)
    {
      permute(length-1,string+1,depth+1);
      rotate(length,string);
    }
  }

    if (source)
    {
      strcpy(source,*argv);
      printf("\nPermuting \"%s\"\n",source);

      permute(strlen(source),source,0);

      free(source);
    }
  }
  return EXIT_SUCCESS;

- --
Lew Pitcher

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12

Having excluded comp.lang.c++ you should first try to write your
algorithm. comp.lang.c does not generally help with algorithms,
comp.programming and alt.comp.lang.c-c++ might, check the groups out to
see. comp.lang.c discusses the C language and helps people with C problems.

Then, post specific questions rather than just asking someone to help
you writing it. A lot of us could write the function in less time that
it would take to explain it to you, but this would not help you to learn.

If you don't know where to start, then I suggest you start off by trying
to write all the permutations of a short string by hand rather than
trying to write a program to do it. Then you can analyse how you did it
and try to formalise that in to an algorithm.

[...]

I have implemented a system like that below:

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

typedef unsigned long long ull;

/* calculate factorial of given number */
ull fact(ull a)
{
   ull result = 1;
   while(a) result *= a--;
   return result;

   for(p = rs; *p; p++)
   {
     np = np / len;
     lt = nm / np;
     nm = nm % np;

     temp = p[0];
     p[0] = p[lt];
     p[lt] = temp;

     len--;
   }

Permuting "abcde"
abcde
abced
...

http://www.cs.utsa.edu/~wagner/knuth/