Generate next permutation in lexicographic order

permutation.c

int
num_digits (int n)
{
  int r;
  
  for (r = 1, n /= 10; n != 0; n /= 10)
    r++;

  return r;
}

int
next_permutation (int n)
{
  int ndigits;
  int *digits;
  int i, j, k, l;
  int tmp, r;

  r = 0;

  ndigits = num_digits (n);
  digits = malloc (sizeof (int) * ndigits);
  for (i = ndigits - 1; i >= 0; i--)
    {
      digits[i] = n % 10;
      n /= 10;
    }

  /* find k */
  k = -1;
  for (i = 0; i < ndigits - 1; i++)
    if (digits[i] < digits[i + 1])
      k = i;

  /* check if this is the last permutation */
  if (k == -1)
      goto end;

  /* find l */
  for (i = k + 1; i < ndigits; i++)
    if (digits[k] < digits[i])
      l = i;

  /* swap digits[k] and digits[l] */
  tmp = digits[k];
  digits[k] = digits[l];
  digits[l] = tmp;

  /* reverse from digits[k + 1] up to digits[last] */
  for (i = k + 1, j = ndigits - 1; i < j; i++, j--)
    {
      tmp = digits[i];
      digits[i] = digits[j];
      digits[j] = tmp;
    }

  /* construct result */
  for (i = 0; i < ndigits; i++)
    {
      r *= 10;
      r += digits[i];
    }

 end:
  free (digits);
  return r;
}