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.

## No comments:

## Post a Comment