Re: print all permutations of string

Alf P. Steinbach wrote:


When you refer to arithmetic coding of permutations using the factorial
number system, are you talking about an algorithm that assigns a unique
index number to each permutation and can return any individual
permutation given its index number?

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;
}

/* generates a permutation of str and stores it in 'rs'
    the permutation generated is index number 'no'
    of 'np' total permutations (np == fact(strlen(str)) */
void get_perm(char *rs, const char *str, ull no, ull np)
{
   size_t len = strlen(str);
   ull nm = no;
   ull lt;
   char *p;
   char temp;
   strcpy(rs, str);

   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--;
   }
}

void print_all(const char *str)
{
   size_t len = strlen(str);
   char *rs = malloc(len + 1);
   ull np = fact(len);
   ull i;
   if(!rs)
   {
     fprintf(stderr, "Error allocating memory\n");
   }
   else for(i = 0; i < np; i++)
   {
     get_perm(rs, str, i, np);
     printf("%4lld: %s\n", i, rs);
   }
}

int main(int argc, char **argv)
{
   if(argc == 2)
   {
     print_all(argv[1]);
   }
   else
   {
     fprintf(stderr, "Error: require one argument for"
                     " string to permute\n");
   }
   return 0;
}