MOS substitution: Difference between revisions

Inthar (talk | contribs)
No edit summary
Tags: Mobile edit Mobile web edit
Inthar (talk | contribs)
 
(19 intermediate revisions by the same user not shown)
Line 1: Line 1:
'''MOS substitution''' is a procedure for obtaining a ternary (3 step sizes) scale from two [[MOS]] patterns. It consists of substituting the step pattern of one MOS pattern (called the filling MOS), scale step for scale step, for all occurrences of a chosen step size of another MOS pattern (called the template MOS). Unlike MV3 scales, a MOS substitution scale may have any combination of step sizes.
'''MOS substitution''' is a procedure for obtaining a ternary (3 step sizes) scale from two [[MOS]] patterns. It consists of substituting the step pattern of one MOS pattern (called the ''filling MOS''), scale step for scale step, for all occurrences of a chosen step size of another MOS pattern (called the ''template MOS''). Unlike MV3 scales, a MOS substitution scale may have any combination of step sizes.


[[Aberrismic theory]] uses MOS substitution. In fact, groundfault reports having come up with a similar concept but not following up on it.
[[Aberrismic theory]] uses MOS substitution. In fact, groundfault reports having come up with a similar concept but not following up on it.
Line 32: Line 32:
|}
|}


== Conventions ==
== Math notation ==
{{User:Inthar/Template:Notation}}
{{User:Inthar/Template:Notation}}
* Boldface Latin variables are step sizes, and <math>\mathbf{L} >  \mathbf{m} > \mathbf{s} > \mathbf{0}.</math> <math>\mathbf{0}</math> denotes the zero step (0 cents).
* Boldface Latin variables are step sizes, and <math>\mathbf{L} >  \mathbf{m} > \mathbf{s} > \mathbf{0}.</math> <math>\mathbf{0}</math> denotes the zero step (0 cents).
Line 43: Line 43:


== Formal definition ==
== Formal definition ==
Suppose ''a'', ''b'', and ''c'' are positive integers. Suppose that the noncircular binary word ''t''('''x''', '''X''') is the brightest mode of the MOS scale word with step signature ''a'''''x'''(''b'' + ''c'')'''X''' when treating '''x''' as larger than '''X''', and that the noncircular binary word ''f''('''y''', '''z''') is one rotation of the MOS scale word with step signature ''b'''''y'''''c'''''z'''. Then the result of replacing the ''i''th occurrence of '''X''' in ''t'' replaced with the ''i''th letter of ''f'' for 0 &le; ''i'' < |''f''|, treated as a circular word, is said to be a ''MOS substitution scale word'' with ''template MOS'' ''a'''''x'''(''b'' + ''c'')'''X''' and ''filling MOS'' ''b'''''y'''''c'''''z''', or in shorthand, a "subst&nbsp;''a'''''x'''(''b'''''y'''''c'''''z''')". If ''f'' is the ''k''th brightest mode, this particular circular word is denoted subst&nbsp;''a'''''x'''(''b'''''y'''''c'''''z''' (''b'' + ''c'' - ''k'')|(''k'' - 1)) (using [[simplified UDP]] for the mode of ''f'').
A ternary scale word ''w''('''x'''<sub>1</sub>, '''x'''<sub>2</sub>, '''x'''<sub>3</sub>) is a ''MOS substitution'' scale word if there exists a permutation <math>\pi \in S_3</math> such that the following holds:
* identifying '''x'''<sub>π(1)</sub> and '''x'''<sub>π(2)</sub> results in a MOS (called the ''template MOS'') and
* deleting all instances of '''x'''<sub>π(3)</sub> (called the ''slot letter'') results in a MOS (called the ''filling MOS'').


== Original derivation ==
== Original derivation ==
Line 52: Line 54:
In the original aberrismic-informed context, say that <math>d = (a, c) > 1.</math> Consider the MOS word <math>(a + c)\mathbf{X}b\mathbf{m}</math>, which we call the ''template MOS''. Since the "most even" arrangement (in the sense of [[distributional evenness]]) of <math>a</math>-many <math>\mathbf{L}</math> steps and <math>c</math>-many <math>\mathbf{s}</math> steps is the MOS <math>a\mathbf{L}b\mathbf{s}</math> (which will in general be a non-[[primitive]] MOS), this method prescribes following the latter MOS, called the ''filling MOS'', to fill in the <math>\mathbf{X}</math> steps. Fixing a choice of which <math>\mathbf{X}</math> in the MOS <math>(a + c)\mathbf{X}b\mathbf{m}</math> you start from, we can choose one of <math>(a+c)/d</math> modes of <math>a \mathbf{L} c \mathbf{s}.</math> If <math>a = c</math>, we obtain a balanced (thus MV3) ternary scale; when in addition <math>b</math> is odd, the scale is also SV3 and chiral, and we recover the two chiralities from the two modes of <math>a\mathbf{L}a\mathbf{s}</math>. Of course, one may do this using template MOS <math>a\mathbf{L}(b + c)\mathbf{X}</math> and the <math>(b, c)</math>-multiperiod filling MOS <math>b\mathbf{m} c\mathbf{s}</math> instead. This article denotes the resulting scale <math>\mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k):</math>  
In the original aberrismic-informed context, say that <math>d = (a, c) > 1.</math> Consider the MOS word <math>(a + c)\mathbf{X}b\mathbf{m}</math>, which we call the ''template MOS''. Since the "most even" arrangement (in the sense of [[distributional evenness]]) of <math>a</math>-many <math>\mathbf{L}</math> steps and <math>c</math>-many <math>\mathbf{s}</math> steps is the MOS <math>a\mathbf{L}b\mathbf{s}</math> (which will in general be a non-[[primitive]] MOS), this method prescribes following the latter MOS, called the ''filling MOS'', to fill in the <math>\mathbf{X}</math> steps. Fixing a choice of which <math>\mathbf{X}</math> in the MOS <math>(a + c)\mathbf{X}b\mathbf{m}</math> you start from, we can choose one of <math>(a+c)/d</math> modes of <math>a \mathbf{L} c \mathbf{s}.</math> If <math>a = c</math>, we obtain a balanced (thus MV3) ternary scale; when in addition <math>b</math> is odd, the scale is also SV3 and chiral, and we recover the two chiralities from the two modes of <math>a\mathbf{L}a\mathbf{s}</math>. Of course, one may do this using template MOS <math>a\mathbf{L}(b + c)\mathbf{X}</math> and the <math>(b, c)</math>-multiperiod filling MOS <math>b\mathbf{m} c\mathbf{s}</math> instead. This article denotes the resulting scale <math>\mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k):</math>  


<math>\displaystyle{ \mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k) := \mathsf{subst}\left( a\mathbf{w}(b + c)\mathbf{X}(0) , \mathbf{X}, b\mathbf{y}c\mathbf{z}(k) \right) }</math>
<math>\displaystyle{\mathsf{subst}\left( a\mathbf{w}(b + c)\mathbf{X}(0) , \mathbf{X}, b\mathbf{y}c\mathbf{z}(k) \right) }</math>
 
For brevity, this should usually be written:
 
<math>\mathsf{subst} \ a\mathbf{x}\left(b\mathbf{y}\,c\mathbf{z} \ k\,\vert\,b+c-1-k\right),</math>
 
using [[simplified UDP]] for the filling MOS.


Here <math>\mathbf{z}</math> is the new step size inserted, <math>\mathbf{y}</math> is the step size in the starting MOS identified with <math>\mathbf{z}</math> by the template MOS, and <math>k</math> is the brightness of the mode of the filling MOS used (<math>k = 0</math> corresponds to the darkest mode; the conventional understanding of "brightness" makes sense as <math>\mathbf{L}</math> (resp. <math>\mathbf{m}</math>) > <math>\mathbf{s}</math>).
Here <math>\mathbf{z}</math> is the new step size inserted, <math>\mathbf{y}</math> is the step size in the starting MOS identified with <math>\mathbf{z}</math> by the template MOS, and <math>k</math> is the brightness of the mode of the filling MOS used (<math>k = 0</math> corresponds to the darkest mode; the conventional understanding of "brightness" makes sense as <math>\mathbf{L}</math> (resp. <math>\mathbf{m}</math>) > <math>\mathbf{s}</math>).
== Denoting modes of a MOS substitution scale ==
Just as rotating the filling MOS while fixing the mode of the template MOS serves to distinguish different MOS substitution scales, we take the mode of the template MOS (treating the slot letter as the smaller step) and write it in UDP or simplified UDP to indicate the mode of a given MOS substitution scale.
For example: Taking the 5|5 mode of the template MOS in {{nowrap|subst 5'''L'''(2'''m'''4'''s''' 2{{pipe}}0)}} ('''LmLsLsLmLss''') yields the mode '''sLmLsLsLmLs''', denoted {{nowrap|"subst 5'''L'''(2'''m'''4'''s''' 2{{pipe}}0) 5{{pipe}}5}}".


== Examples ==
== Examples ==
Line 184: Line 175:


In particular, all [[monotone-MOS scale]]s (i.e. such that the results of {{nowrap|'''L''' {{=}} '''m''' | '''m''' {{=}} '''s'''}}, and {{nowrap|'''s''' {{=}} '''0'''}} temperings are MOSes) arise from MOS substitution in this way.
In particular, all [[monotone-MOS scale]]s (i.e. such that the results of {{nowrap|'''L''' {{=}} '''m''' | '''m''' {{=}} '''s'''}}, and {{nowrap|'''s''' {{=}} '''0'''}} temperings are MOSes) arise from MOS substitution in this way.
=== If a ternary scale satisfies all three possible MOS-substitution types, then it is pairwise-MOS and deletion-MOS ===
This fact is immediate. (See [[pairwise-MOS]] and [[deletion-MOS]].)
Corollary (by [[Ternary scale theorems]]): Such a scale is [[Fraenkel word|Fraenkel]], [[odd-regular]], or [[even-regular]].


=== If the template MOS is primitive, MOS substitution yields binary well-formed generator sequences ===
=== If the template MOS is primitive, MOS substitution yields binary well-formed generator sequences ===
Line 190: Line 185:
Consider the mode of the template MOS <math>T = T(\mathbf{m},\mathbf{X}) = (a+c)\mathbf{X}b\mathbf{m}(0).</math> This is the mode of <math>T</math> that has the most <math>\mathbf{X}</math> steps near the end. If <math>T</math> is [[primitive]], let <math>r</math> be the count of <math>\mathbf{X}</math> steps in a chosen (reduced) generator of <math>T.</math> Since <math>r</math> must be coprime to <math>a+c,</math> <math>r</math>-steps in the filling MOS <math>F = a\mathbf{L}c\mathbf{s}(k)</math> come in exactly 2 sizes, <math>i\mathbf{L}+j\mathbf{s}</math> and <math>(i-1)\mathbf{L}+(j+1)\mathbf{s}.</math> Since the detempering of the imperfect generator of <math>T</math> occurs only once in <math>S</math>, <math>S</math> admits a particularly elegant well-formed binary (using two distinct generators) [[generator sequence]] of length <math>q = \frac{a+c}{\gcd(a,c)},</math> the period of the filling MOS. The generator sequence corresponds to the circle of <math>r</math>-steps in the filling MOS. Letting <math>\mathsf{GS}(g_1, ..., g_{q})</math> be this generator sequence, <math>g_j</math> is either <math>p\mathbf{m} + i\mathbf{L} + j\mathbf{s}</math> or <math>p\mathbf{m} + (i-1)\mathbf{L} + (j+1)\mathbf{s},</math> according as the <math>j</math>-th <math>r</math>-step in the sequence of stacked <math>r</math>-steps on the chosen mode of <math>F</math> is <math>i\mathbf{L} + j\mathbf{s}</math> or <math>(i-1)\mathbf{L} + (j+1)\mathbf{s}.</math> (We could have chosen to use the mode of <math>T</math> on the other extreme of its generator arc instead, which corresponds to taking the circle of <math>(a+c - r)</math>-steps in <math>F</math> and is thus also valid.) The generator of the template MOS serves as the "guide generator" for this generator sequence.
Consider the mode of the template MOS <math>T = T(\mathbf{m},\mathbf{X}) = (a+c)\mathbf{X}b\mathbf{m}(0).</math> This is the mode of <math>T</math> that has the most <math>\mathbf{X}</math> steps near the end. If <math>T</math> is [[primitive]], let <math>r</math> be the count of <math>\mathbf{X}</math> steps in a chosen (reduced) generator of <math>T.</math> Since <math>r</math> must be coprime to <math>a+c,</math> <math>r</math>-steps in the filling MOS <math>F = a\mathbf{L}c\mathbf{s}(k)</math> come in exactly 2 sizes, <math>i\mathbf{L}+j\mathbf{s}</math> and <math>(i-1)\mathbf{L}+(j+1)\mathbf{s}.</math> Since the detempering of the imperfect generator of <math>T</math> occurs only once in <math>S</math>, <math>S</math> admits a particularly elegant well-formed binary (using two distinct generators) [[generator sequence]] of length <math>q = \frac{a+c}{\gcd(a,c)},</math> the period of the filling MOS. The generator sequence corresponds to the circle of <math>r</math>-steps in the filling MOS. Letting <math>\mathsf{GS}(g_1, ..., g_{q})</math> be this generator sequence, <math>g_j</math> is either <math>p\mathbf{m} + i\mathbf{L} + j\mathbf{s}</math> or <math>p\mathbf{m} + (i-1)\mathbf{L} + (j+1)\mathbf{s},</math> according as the <math>j</math>-th <math>r</math>-step in the sequence of stacked <math>r</math>-steps on the chosen mode of <math>F</math> is <math>i\mathbf{L} + j\mathbf{s}</math> or <math>(i-1)\mathbf{L} + (j+1)\mathbf{s}.</math> (We could have chosen to use the mode of <math>T</math> on the other extreme of its generator arc instead, which corresponds to taking the circle of <math>(a+c - r)</math>-steps in <math>F</math> and is thus also valid.) The generator of the template MOS serves as the "guide generator" for this generator sequence.


=== If the template is a primitive MOS, and for some perfect generators <math>p_T, p_F, \ r := \left|p_T\right|_\mathbf{X} = \left|p_F\right|,</math> then MOS substitution yields a quasi-parallelogram in the lattice ===
=== If the template is a primitive MOS, and for some perfect generators <math>p_T, p_F, \ r := \left|p_T\right|_\mathbf{X} = \left|p_F\right|,</math> then MOS substitution yields a parallelogram substring in the lattice ===
With the additional assumption that the number of '''X''' letters in a perfect generator ''p''<sub>''T''</sub> of the template MOS be a generator class of the filling MOS, the generator sequence yields ''q'' parallel chains ''C''<sub>1</sub>,  
With the additional assumption that the number of '''X''' letters in a perfect generator ''p''<sub>''T''</sub> of the template MOS be a generator class of the filling MOS, the generator sequence yields ''q'' parallel chains ''C''<sub>1</sub>,  
..., ''C''<sub>''q''</sub> of the aggregate generator, the sum of the generators in the GS. The offset between ''C''<sub>''i''</sub> and ''C''<sub>''i''+1</sub> is equal to subst(''p''<sub>''T''</sub>, '''X''', ''p''<sub>''F''</sub>), where ''p''<sub>''T''</sub> and ''p''<sub>''F''</sub> are perfect generators (of appropriate lengths) of the template and filling MOSes, respectively. The aggregate generator is  subst((''p''<sub>''T''</sub>)<sup>''q''</sup>, '''X''', ''G''<sup>''r''</sup>), where ''G'' is the period of the filling MOS.
..., ''C''<sub>''q''</sub> of the aggregate generator, the sum of the generators in the GS. The offset between ''C''<sub>''i''</sub> and ''C''<sub>''i''+1</sub> is equal to subst(''p''<sub>''T''</sub>, '''X''', ''p''<sub>''F''</sub>), where ''p''<sub>''T''</sub> and ''p''<sub>''F''</sub> are perfect generators (of appropriate lengths) of the template and filling MOSes, respectively. The aggregate generator is  subst((''p''<sub>''T''</sub>)<sup>''q''</sup>, '''X''', ''G''<sup>''r''</sup>), where ''G'' is the period of the filling MOS.
Line 198: Line 193:
* the imperfect generator of the filling MOS corresponds to looping back to ''C''<sub>1</sub> but on the next note of ''C''<sub>1</sub>, so it and the ''q'' &minus; 1 notes thereafter are advanced by 1 note from any predecessor notes in the chains.
* the imperfect generator of the filling MOS corresponds to looping back to ''C''<sub>1</sub> but on the next note of ''C''<sub>1</sub>, so it and the ''q'' &minus; 1 notes thereafter are advanced by 1 note from any predecessor notes in the chains.


Hence these particular MOS substitution scales satisfy a property that we call ''quasi-parallelogram''. An '''e'''-equivalent scale is a ''quasi-parallelogram'' if there exist integers ''m'' > 0, ''n'' > 0, 0 &le; ''a'' < ''n'', 0 &le; ''b'' < ''n'', a vector '''a''', and two linearly independent vectors '''v''' and '''w''' such that the set of notes in the scale as a subset of the lattice of '''e'''-equivalent pitches is  
Hence these particular MOS substitution scales satisfy a property that we call ''[[parallelogram substring scale|parallelogram substring]]''. An '''e'''-equivalent scale is a ''parallelogram substring'' if there exist integers ''m'' > 0, ''n'' > 0, 0 &le; ''a'' < ''n'', 0 &le; ''b'' < ''n'', a vector '''a''', and two linearly independent vectors '''v''' and '''w''' such that the set of notes in the scale as a subset of the lattice of '''e'''-equivalent pitches is  


<math>
<math>
Line 214: Line 209:
In the above case, {{nowrap| ''n'' {{=}} ''q'' | '''v''' {{=}} subst(''p''<sub>''T''</sub>, '''X''', ''p''<sub>''F''</sub>) | and '''w''' {{=}} subst((''p''<sub>''T''</sub>)<sup>''q''</sup>, '''X''', ''G''<sup>''r''</sup>) (the aggregate generator)}}.
In the above case, {{nowrap| ''n'' {{=}} ''q'' | '''v''' {{=}} subst(''p''<sub>''T''</sub>, '''X''', ''p''<sub>''F''</sub>) | and '''w''' {{=}} subst((''p''<sub>''T''</sub>)<sup>''q''</sup>, '''X''', ''G''<sup>''r''</sup>) (the aggregate generator)}}.


The converse is false, as the scale in 5 letters [9/8 28/27 9/8 64/63 9/8 28/27 243/224 28/27 64/63 567/512 64/63] is a quasi-parallelogram.
The converse is false, as the scale in 5 letters [9/8 28/27 9/8 64/63 9/8 28/27 243/224 28/27 64/63 567/512 64/63] is a parallelogram substring.


=== MOS substitution scales have block balance at most 2 ===
=== MOS substitution scales have block balance at most 2 ===
Line 222: Line 217:


Case 2: Neither of ''k'' and {{nowrap|''k'' + 1}} equals ({{nowrap|''b'' + ''c''}}). Here, if '''Y''' occurs ''j'' or {{nowrap|''j'' + 1}} times in a window of size ''k'', then '''Y''' occurs {{nowrap|''j'' + 1}} or {{nowrap|''j'' + 2}} times in a window of size {{nowrap|''k'' + 2}}.
Case 2: Neither of ''k'' and {{nowrap|''k'' + 1}} equals ({{nowrap|''b'' + ''c''}}). Here, if '''Y''' occurs ''j'' or {{nowrap|''j'' + 1}} times in a window of size ''k'', then '''Y''' occurs {{nowrap|''j'' + 1}} or {{nowrap|''j'' + 2}} times in a window of size {{nowrap|''k'' + 2}}.
=== Ternary parallelogram scales are MOS substitution scales ===
:''Main article: [[Ternary parallelogram scales are MOS substitution]]''


== MOS substitution scales and RTT ==
== MOS substitution scales and RTT ==
Line 247: Line 245:
     scale = subst_step_sizes(word, {"X": sizeX, "Y": sizeY, "Z": sizeZ})
     scale = subst_step_sizes(word, {"X": sizeX, "Y": sizeY, "Z": sizeZ})
     return scale
     return scale
</syntaxhighlight>
== Code ==
Rust code for generating MOS substitution scales:
<syntaxhighlight lang="rs">
pub type Letter = usize;
/// Return gcd(a, b) and the Bezout coefficients: (g, x, y).
pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    let (mut r, mut old_r) = (a, b);
    let (mut s, mut old_s) = (1, 0);
    let (mut t, mut old_t) = (0, 1);
    while r != 0 {
        let quotient = old_r / r;
        (old_r, r) = (r, old_r - quotient * r);
        (old_s, s) = (s, old_s - quotient * s);
        (old_t, t) = (t, old_t - quotient * t);
    }
    (old_r, old_s, old_t)
}
/// Return the gcd.
pub fn gcd(a: i64, b: i64) -> i64 {
    extended_gcd(a, b).0
}
// Compute `n % abs(m)`
fn modulo(n: i64, m: i64) -> i64 {
    ((n % m) + m) % m
}
/// Return *x* such that (*xa*) mod *b* = 1.
pub fn modinv(a: i64, b: i64) -> Result<i64, String> {
    let (gcd, x, _) = extended_gcd(a, b);
    if gcd == 1 {
        Ok(modulo(x, b))
    } else {
        Err("Non-coprime generator error".to_string())
    }
}
/// The rotation required from the current word to the
/// lexicographically least mode of a word.
/// Booth's algorithm requires at most 3*n* comparisons and *n* storage locations where *n* is the input word's length.
/// See Booth, K. S. (1980). Lexicographically least circular substrings.
/// Information Processing Letters, 10(4-5), 240–242. doi:10.1016/0020-0190(80)90149-0
pub fn booth(scale: &[Letter]) -> usize {
    let n = scale.len();
    // `f` is the failure function of the least rotation; `usize::MAX` is used as a null value.
    // null indicates that the failure function does not point backwards in the string.
    // `usize::MAX` will behave the same way as -1 does, assuming wrapping unsigned addition
    let mut f = vec![usize::MAX; 2 * n];
    let mut k: usize = 0;
    // `j` loops over `scale` twice.
    for j in 1..2 * n {
        let mut i = f[j - k - 1];
        while i != usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
            // (1) If the jth letter is less than s[(k + i + 1) % n] then change k to j - i - 1,
            // in effect left-shifting the failure function and the input string.
            // This appropriately compensates for the new, shorter least substring.
            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
                k = j.wrapping_sub(i).wrapping_sub(1);
            }
            i = f[i];
        }
        if i == usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
            // See note (1) above.
            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
                k = j;
            }
            f[j - k] = usize::MAX;
        } else {
            f[j - k] = i.wrapping_add(1);
        }
        // The induction hypothesis is that
        // at this point `f[0..j - k]` is the failure function of `s[k..(k+j)%n]`,
        // and `k` is the lexicographically least subword of the letters scanned so far.
    }
    k
}
/// Rotate an array. Returns a Vec.
pub fn rotate<T: std::clone::Clone>(slice: &[T], degree: usize) -> Vec<T> {
    let degree = degree % slice.len();
    if degree == 0 {
        slice.to_vec()
    } else {
        [&slice[degree..slice.len()], &slice[0..degree]].concat()
    }
}
/// The lexicographically least mode of a word (where the letters are in their usual order).
pub fn least_mode(scale: &[Letter]) -> Vec<Letter> {
    rotate(scale, booth(scale))
}
/// Delete all instances of one letter.
pub fn delete(scale: &[Letter], letter: Letter) -> Vec<Letter> {
    scale.iter().filter(|x| **x != letter).cloned().collect()
}
/// Letterwise substitution for scale words.
///
/// Note: This function does not fail even if the number of times `x` occurs in `template`
/// does not divide `filler.len()`.
pub fn subst(template: &[Letter], x: Letter, filler: &[Letter]) -> Vec<Letter> {
    let mut ret = vec![];
    let mut i: usize = 0;
    if !filler.is_empty() {
        for &letter in template {
            if letter == x {
                // Use the currently pointed-to letter of `filler` in place of `x`.
                ret.push(filler[i % filler.len()]);
                // Only update `i` when an `x` is replaced.
                i += 1;
            } else {
                ret.push(letter);
            }
        }
    } else {
        // If `filler` is empty, we return `template` but with all `x`s removed.
        return delete(template, x);
    }
    ret
}
/// Return the darkest mode of the MOS axby and the dark generator, using the Bresenham line algorithm.
/// We chose the darkest mode rather than the brightest because this is the mode with brightness == 0.
pub fn darkest_mos_mode_and_gen_bresenham(a: usize, b: usize) -> (Vec<Letter>, Vec<usize>) {
    let d = gcd(a as i64, b as i64) as usize;
    if d == 1 {
        let count_gen_steps = modinv(a as i64, a as i64 + b as i64)
                .expect("The dark generator is a (|L|⁻¹ mod |scale|)-step, since stacking it |L| times results in the s step (mod period).")
                as usize;
        let mut result_scale: Vec<usize> = vec![];
        // Start from the origin (0, 0)
        let (mut current_x, mut current_y) = (0usize, 0usize);
        while (current_x, current_y) != (a, b) {
            if a * (current_y) >= b * (current_x + 1) {
                // If going east (making a (1, 0) step) doesn't lead to going below the line y == b/a*x,
                current_x += 1; // append the x step and reflect the change in the plane vector.
                result_scale.push(0);
            } else {
                // Else, make a (0, 1) step.
                current_y += 1;
                result_scale.push(1);
            }
        }
        // Get the dark generator. We know how many steps and that this will give the perfect generator, not the
        // augmented one, since we just got the darkest mode.
        let result_gen = {
            let mut gen = vec![0, 0, 0];
            for i in 0..count_gen_steps {
                if result_scale[i] < 3 {
                    gen[result_scale[i]] += 1;
                }
            }
            gen
        };
        (result_scale, result_gen)
    } else {
        let (prim_mos, gen) = darkest_mos_mode_and_gen_bresenham(a / d, b / d);
        (prim_mos.repeat(d), gen)
    }
}
/// Return the collection of all MOS substitution scales `subst n0 x (n1 y n2 z)`
/// where the template MOS is assumed to have step signature `n0*0 (n1 + n2)*X` (`X` is the slot letter)
/// and the filling MOS has step signature `n1*1 n2*2`.
fn mos_substitution_scales_one_perm(n0: usize, n1: usize, n2: usize) -> Vec<Vec<Letter>> {
    let (template, _) = darkest_mos_mode_and_gen_bresenham(n0, n1 + n2);
    let (filler, gener) = darkest_mos_mode_and_gen_bresenham(n1, n2);
    let filler = filler.into_iter().map(|x| x + 1).collect::<Vec<_>>();
    let gener_size = gener.len();
    (0..(n1 + n2))
        .map(|i| {
            subst(
                &template,
                1usize,
                &rotate(&filler, (i * gener_size) % filler.len()),
            )
        })
        .collect()
}
/// The set of all [MOS substitution](https://en.xen.wiki/w/User:Inthar/MOS_substitution) ternary scales.
pub fn mos_substitution_scales(sig: &[usize]) -> Vec<Vec<Letter>> {
    let (n0, n1, n2) = (sig[0], sig[1], sig[2]);
    // Only need 3 permutations of (0, 1, 2) for the MOS substitution patterns n0*_ (n1*_ n2*_)
    let redundant_list = [
        // n0L (n1m n2s)
        mos_substitution_scales_one_perm(n0, n1, n2),
        // n1m (n0L n2s)
        mos_substitution_scales_one_perm(n1, n2, n0)
            .into_iter()
            .map(|scale| scale.into_iter().map(|x| (x + 1) % 3).collect())
            .collect(),
        // n2s (n0L n1m)
        mos_substitution_scales_one_perm(n2, n0, n1)
            .into_iter()
            .map(|scale| {
                scale
                    .into_iter()
                    .map(|x| if x == 0 { 2 } else { (x - 1) % 3 })
                    .collect()
            })
            .collect(),
    ]
    .concat();
    // Canonicalize every scale and remove duplicates
    let mut canonicalized_list: Vec<_> = redundant_list
        .into_iter()
        .map(|scale| least_mode(&scale))
        .collect();
    canonicalized_list.sort();
    canonicalized_list.dedup();
    canonicalized_list
}
fn main() {
    for scale in mos_substitution_scales(&[5, 2, 4]) {
        println!("{:?}", scale);
    }
    /*
        [0, 0, 1, 2, 0, 2, 0, 1, 2, 0, 2]
        [0, 0, 2, 0, 1, 2, 0, 0, 2, 1, 2]
        [0, 0, 2, 0, 1, 2, 0, 2, 0, 1, 2]
        [0, 0, 2, 0, 2, 1, 0, 2, 0, 1, 2]
        [0, 0, 2, 0, 2, 1, 0, 2, 0, 2, 1]
        [0, 0, 2, 1, 0, 2, 0, 0, 2, 1, 2]
        [0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2]
        [0, 0, 2, 1, 0, 2, 0, 2, 0, 1, 2]
        [0, 0, 2, 1, 0, 2, 0, 2, 1, 0, 2]
        [0, 1, 0, 2, 0, 2, 0, 1, 0, 2, 2]
    */
}
</syntaxhighlight>
</syntaxhighlight>