/* Problem 1--Generating Product Codes
   The trick is to start at the end of the string and move backwards.
   When you find a letter less than the one following it, you move the
   smallest letter to the right and larger than the one to be replaced
   into position and resort all the letters to the right. */

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

int main (int argc, char **argv);
void Process (char *word);
int ccmp (const void *a, const void *b);

FILE *in, *out;

int main (int argc, char **argv) {

  char word[33];

 in = fopen ("prob1.in","r");
 out = fopen ("prob1.out","w"); /* Read in words until EOF */
 while (EOF!=fscanf (in,"%s",word)) Process (word);
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/*Process accepts a word and prints out the successor, if there is one*/
void Process (char *word) {

  int l = strlen (word), smallpos=0, i, j;
  char smallest = 'a', t;
                      /* work backwards finding where to reorder */
 for (i=l-1;i>0;i--) if (word[i]>word[i-1]) break;
 if (i==0) { /* Made it all the way back */
  fprintf (out,"*** No Successor ***\n");
  return;
 }
 for (j=l-1;j>=i;j--) /* find the smallest letter larger than the one */
  if (word[j]>word[i-1] && word[j] < smallest) { /* to be replaced */
   smallpos = j;
   smallest = word[j];
  }
 t = word[i-1]; /* move that letter into position */
 word[i-1] = word[smallpos];
 word[smallpos] = t;
 qsort(&(word[i]),l-i,sizeof(char),ccmp); /* sort the remainder */
 fprintf (out,"%s\n",word);
}

/* ccmp is a standard char comparion */
int ccmp (const void *a, const void *b) {

 return *(char*)a - *(char*)b;
}