1237. Every String of Digits That Never Goes Down
Print every string of n digits, each from 1 to d, in which no digit is
smaller than the one before it, one per line, in LEXICOGRAPHIC order.
n = 2, d = 3
11
12
13
22
23
33
## Why the order has to be pinned, and pinned without naming a program
A set of answers has no order. If a statement says only "print them all", two correct programs produce two different outputs and no automated check can tell a correct program from a broken one. So the order is part of the specification.
The second trap is pinning it as "the order your search finds them in". That names a program rather than a rule, and it is not a specification: a search that tries its options in a different sequence finds the same answers in a different order and is equally entitled to call itself correct. The rule below mentions no search.
The rule here is ordinary lexicographic order, which is unambiguous for strings of the same length.
## What most people try first
Generate all d^n strings and keep the non-decreasing ones. At n = 5, d = 9
that is 59049 strings to print 1287, so forty-five out of forty-six are thrown
away. And the waste grows: the fraction kept is
C(d + n - 1, n) / d^n, which falls as n grows.
## Generating directly
The constraint is that each digit is at least the one before, so carry the previous digit as the floor for the next one:
go(i, low):
if i == n: print the string; return
for digit in low .. d:
write digit at position i; go(i + 1, digit)
with low starting at 1. Every leaf is an answer, so nothing is wasted, and
trying the digits in increasing order makes the output lexicographic.
## Why the output is lexicographic
Two different answers differ at some first position, and the recursion tries the smaller digit there first and explores that whole branch before the larger one. So the answer with the smaller digit at the first difference is printed first, which is lexicographic order.
## How many there are
A non-decreasing string of length n over d symbols is the same thing as a
MULTISET of size n drawn from d kinds, because the string is determined by
how many of each digit it contains and the order is forced. The number of such
multisets is C(d + n - 1, n), by the standard stars-and-bars argument: lay out
n stars and d - 1 bars, and read the number of stars between consecutive bars
as the count of each digit.
At n = 5, d = 9 that is C(13, 5) = 1287, which the tests check.
## The settled boundaries
d = 1 leaves exactly one answer, all 1s. n = 1 gives d answers, the
digits in increasing order. There is always at least one answer, the all-1
string, so nothing special is printed for an empty result.
## Cost
One node per valid prefix with every leaf an answer, so the work is proportional to the output.
Constraints - `1 ≤ n ≤ 5` - `1 ≤ d ≤ 9`
Input
A single line containing two integers n and d.
Output
Print every non-decreasing string on its own line in lexicographic order. There is always at least one.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.