----- Original Message -----
From: "MADHUSUDHAN JOSHI" <madhusudhan21@yahoo.com>
To: <vijoeyz@hotpop.com>
Sent: Friday, February 13, 2004 10:12 AM
Subject: hi--man--HOwz you


> Hi vijay...
> how r u doing????
>
> can u help me out how to print all combinations of a
> string???
>
> bye and regds,
>
> Joshi
> =====
> A man can still go a long way when he is tired,
> Dont give up.


    It can be observed that the number of combinations of string, of length N,
is N!.  Consider an example:

         string:  123
         Length:  3
    Combination:  3! = 6
         Output:  123  132  321  312  231  213

    Following is a program to print all the combination a string:

 1  /*
 2   * str_combi.c  -   Print all the combinations of a string
 3   * Author       -   Vijay Kumar R Zanvar <vijoeyz@hotmail.com>
 4   * Date         -   Feb 16, 2004
 5   */
 6
 7  #include <stdlib.h>
 8  #include <stdio.h>
 9  #include <string.h>
10
11  void
12  string_combi ( char * s, int len )
13  {
14      int         i;
15      char        tmp;
16      static int  j;
17      static char *p;
18
19      if ( !p )
20          p = s;
21
22      for ( i = 1; i <= len; i++ )
23      {
24          if ( len > 2 )
25              string_combi ( s+1, len-1 );
26          else
27          {
28              j++;
29              printf ( "%d: %s\t", j, p );
30              if ( !( j%10 ) )
31                  puts ( "" );
32          }
33          if ( i < len )
34          {
35              tmp = s[len-i];
36              s[len-i] = s[0];
37              s[0] = tmp;
38          }
39      }
40      return;
41  }
42
43  int
44  main()
45  {
46      char s[50];
47
48      printf("\n Enter String : ");
49      scanf("%s%*c", s);
50      string_combi ( s, strlen ( s ) );
51
52      return EXIT_SUCCESS;
53  }
54
    Note the following points:

    *   p always points the beginning of the string. (line 17)

    *   Independent of the logic, the printf statement (line 29) always prints
        the entire string.  It is our task to manipulate the string.

    *   To achieve the count of N!, the string_combi () function uses
        "iterative-recursion" method.  A property of a recursive function
        is that it breaks down the problem into atomic states, solve it, and
        later merge all the atomic solutions to form the final solution.

        The atomic state of string_combi() is a string of length two.  This
        condition is checked at the line 24.  The string is broken as long as
        it's length is greater than 2.

    *   The first and last characters of the string are always swapped if the
        condition of line 33 is satisfied.

    *   Keeping the above points in mind, try tracing the program.