Efficient generation (using MATLAB) of the subset of all permutations that are in alphabetical order

Question

Suppose, for example, that I have $d=4$ dials on a lock each with $s=3$ possible settings: $a, b, c$. As shown by Ned in this post, the subset of lock permutations that are in alphabetical order in this particular case is:

aaaa
aaab
aaac
aabb
aabc
aacc
abbb
abbc
abcc
accc
bbbb
bbbc
bbcc
bccc
cccc

Can an algorithm be created in MATLAB, which generates the subset of all permutations that are in alphabetical order (or if the settings of the lock are numbers, then in descending order) WITHOUT visiting all possible permutations to check if the particular permutation belongs to the subset?

Answer 1

I do not know how to code in MATLAB, but here is some pseudo code which works:

input:  non-negative integer d and list S of symbols
output: a list of all words of length d, using letters in S, where
        letters appear in the same order they do in S

codes(d,S):
    if d = 0:
        return a list which only contains the empty string.
    if d > 0 and S is empty:
        return the empty list
    else:
        let s  be the last element of S
        let S' be S with s removed
        let L1 = codes(d,S')
        let L2 = codes(d-1,S)
        append the symbol s to then end of each string in L2.
        return the concatenation of L1 and L2