A interview question: the next permutation

Write the code for the following question:

You get an array of digits that represent a number. The digits are unique, such that for every index i in the array there is not index j such that the digit in i is the same as the digit in j (unless j=i). You need to write a function that will give the next number (the smallest number that has this property with its digits and the same digits, that is bigger than the given number). If the given number is the largest, then your function should indicate that there is no next number.

Examples:
* if you get 123 you should return 132
* if you get 4312 you should return 4321
* if you get 12543 you should return 13245
* if you get 21 you cannot return the next number because there is no next number.

OK. This sounds like a task that requires writing an iterator for the next permutation.

For a number (string) with n distinct digits (symbols) there are n! permutation.

n! is recursively defined for every non-negative integer to be:

0! = 1
n! = n*(n-1)!

So, we have a way to see if we wrote down all the permutations of such a number with n digits, by making sure that we wrote n! different numbers with the same digits.

Here are some examples for 1, 2, 3, and 4 digit numbers:

n=1	n=12	n=123	n=1234
1	12	123	1234
	21	132	1243
		213	1324
		231	1342
		312	1423
		321	1432
			2134
			2143
			2314
			2341
			2413
			2431
			3124
			3142
			3214
			3241
			3412
			3421
			4123
			4132
			4213
			4231
			4312
			4321

Observations:

1. when all digits are sorted (from left to right) in a descending order then we have reached the largest number that has the listed property.
2. in order to get the next permutation (the next number) we scan the digits from right to left and seek for the first pair of digits where the left digit in the pair is smaller than the right digit in the pair, replace the left digit of the pair with the smallest digit to its right that is larger than it, and then sort the digits to its right (after the swap) from smallest to largets.

Here's a Perl implementation of that function.

#!/usr/bin/perl
use strict;
use warnings;

print join('', @{get_next([@ARGV])}),"\n";

sub get_next {
  my ($permutation) = @_;
  for (my $i=@$permutation-1; $i>0; --$i) {
     if ($permutation->[$i]>$permutation->[$i-1]) {
        swap($permutation,$i-1,swap_with($permutation,$i-1));
        @$permutation[$i .. @$permutation-1] =
           sort @$permutation[$i .. @$permutation-1];
        return $permutation;
     }
  }
  return [];
}

sub swap_with {
  my ($array_ref,$index) = @_;
  my $candidate=$index+1;
  for (my $i=$index; $i<@$array_ref; ++$i) {
     $candidate=$i
        if ($array_ref->[$i]<$array_ref->[$candidate] and
           $array_ref->[$i]>$array_ref->[$index]);
  }
  return $candidate;
}

sub swap {
  my ($array_ref,$this_index,$that_index) = @_;
  ($array_ref->[$this_index],$array_ref->[$that_index]) =
     ($array_ref->[$that_index],$array_ref->[$this_index]);
}