++LanX for an excellent answer (way faster than my brute force approach).
Allow me one nit-pick:
9! = 362880 possible combinations are checked in a recursive function.
Throwing in a counter shows that sub append_digit is actually called 986,410 times. Took me a while to work out why...
9! is the number of combinations if every number has exactly 9 digits. But we also allow numbers with 1, 2, ..., 8 digits. So the total number of combinations is:
my $p = 9 + # 1 digit
(9 * 8) + # 2 digits
(9 * 8 * 7) + # 3 digits
(9 * 8 * 7 * 6) + # 4 digits
(9 * 8 * 7 * 6 * 5) + # 5 digits
(9 * 8 * 7 * 6 * 5 * 4) + # 6 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3) + # 7 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2) + # 8 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1); # 9 digits
say $p; # = 986,409
(That 1 extra sub call is the first one, when @number is empty.)
:-)
For anyone else trying to understand how this code works, here is my slightly-reworked version which outputs the results in the order found:
my $calls = 0;
my $count = 0;
my @digits;
my @solutions;
append_digit();
print "count: $count\n", join("\n", @solutions), "\n";
print "recursive calls: ", $calls, "\n";
sub append_digit
{
++$calls;
my $number = join '', @digits;
if (@digits && ! grep { $number % $_ } @digits)
{
print "$count: $number\n" unless ++$count % 100;
push @solutions, $number;
}
for my $digit (1 .. 9)
{
next if $digit ~~ @digits;
push @digits, $digit;
append_digit();
pop @digits;
}
}
Hope that’s helpful!
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.