Well-Ordered Numbers In Perl

I was recently asked to solve the problem of printing out a list of all "well-ordered numbers", which is a multi-digit integer for which each digit is less than the digit to its right. For instance, 123 is well-ordered because 1 is less than 2, and 2 is less than 3; but 395 is not well-ordered, because while 3 is less than 9, nine is not less than 5.

This is a subtle problem requiring a clever solution. Certainly there is more than one way to solve this problem, and when the problem was presented to me I did not think of a correct way to solve it. I tried to come up with a series of nested loops which would print the needed strings, but I couldn't get the loops to do what they needed to. Furthermore, it would be possible to brute-force-attack the problem by generating all the numbers, checking each if it is well-ordered, and if so printing it out; but I didn't like that solution because it is inelegant.

For this solution I settled on a recursive approach. This solution is made easier in perl because you can optionally include or exclude the second parameter to the subroutine, something which you can not do in some other languages. If you leave out the second parameter, its value becomes "undefined" in perl parlance, and luckily enough when you sum 1 and undefined in perl, you get 1, which happens to be what I need for this to work. In another language, you might have to check for undefined and explicitly set it to 0 before you could use that value in a math problem.

#!perl



use strict;



&generateWellOrderedNumbers( 8 );



sub generateWellOrderedNumbers {

 my $count = shift;

 my $beginning = shift;

 

 my $lastNumOfBeginning = substr $beginning, -1, 1;

 $count--;

 

 for( my $i = $lastNumOfBeginning+1; $i < 10; $i++ ) {

  my $printstring = $beginning . $i;

  if($count == 0) {

   print $printstring . "\n";

  }

  

  else {

   &generateWellOrderedNumbers($count, $printstring);

  }

 }

}

When this is run from the command line, it prints

12345678

12345679

12345689

12345789

12346789

12356789

12456789

13456789

23456789

In this solution I have a recursive subroutine named generateWellOrderedNumbers. The subroutine takes two parameters, the number of characters that still need to be generated, and a string of numbers already generated. When the subroutine is first seeded, the first parameter is equal to the desired well-ordered number length, and the second parameter is the empty or undefined string, which is why that parameter can be ignored in perl on the first recursion.

The subroutine then loops, starting at one greater than the last digit of the already-built well-ordered number, up to 9, appending that digit to the built number. If no more digits need to be added, which is to say that the number is now at the desired length, then the number is printed; otherwise the subroutine recurses with a decremented length and an augmented built number.

This algorithm works correctly. For the trivial case of a 0-length well-ordered number, it exits without printing anything. In the case of a 1-length well-ordered number, it prints the numbers 1 through 9. For the case of a 9-length well-ordered number, it prints one number: 123456789. For lengths greater than 9, it again exits without printing anything, because there can be no well-ordered numbers longer than 9 digits, since decimal counting systems only have 10 digits, and we aren't using 0 in this solution.