Having discussed the general form of this program with you and written code for it, I have something of an advantage over others. The code to iterate through all solutions is below, and is running on my PC as I type this, at something between 10000 and 20000 iterations/second.
I will be pondering whether there isn't a way to determine how many ways to get the result without actually generating them. I know that you can save one order of magnitude by knowing that your last dial will always have only one acceptable value, so you can just count the number of elements on the next-to-last dial, then iterate to the next incarnation of it.
use strict;
use warnings;
use Algorithm::Loops 'NestedLoops';
use List::Util qw'sum min';
# find all subsets of 1..$N of size $S whose sum is $T:
sub selections {
my ($N, $S, $T, $callback) = @_;
NestedLoops(
[
(sub {
no warnings 'uninitialized';
my $new_t = $T - sum(@_); # Target sum for remaining dials
my $new_s = $S - @_; # Number of remaining dials
# Each dial is > than the one to the left of it
my $min = $_[-1] + 1;
# The value must be large enough that the remaining dials
# can reach the target. The min formula is
my @min_vals = map $N-$_, reverse 1..$new_s-1;
my $s = sum @min_vals;
my $x = $new_t - $s;
if ($x > $min) { $min = $x }
my $max = $N - $new_s;
# The value must be small enough that the remaining dials
# can all increase and still not overshoot the target. The
# max formula is
# x + (x + 1) + ... + (x + S-1) = new_t
# ==> (x * S) + ((S-1)*S/2)
# Solving for x:
$x =int( ($new_t - (($new_s - 1) * $new_s/2))/$new_s );
if ($x < $max) { $max = $x }
[$min .. $max]
}) x $S
],
);
}
my $i = selections(100, 10, 667);
my $solution_count = 0;
while ($i->()) {
++$solution_count;
print "$solution_count iterations\n" if $solution_count % 10_000 ==
+0;
}
Caution: Contents may have been coded under pressure.