|
Tags: Mobile edit Mobile web edit |
| Line 242: |
Line 242: |
| 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> |
|
| |
|