|
|
| Line 188: |
Line 188: |
|
| |
|
| === General algorithm === | | === General algorithm === |
| This is the general algorithm for generating a maximally even scale consisting of x large steps and y small steps (a moment-of-symmetry scale). This algorithm will produce that scale without any prior knowledge of how the scale's steps are ordered. This algorithm is recursive. | | This is the general algorithm for generating a moment of symmetry scale of the form xL ys represented as a string of L's and s's in its brightest mode. This algorithm will produce that scale without any prior knowledge of how the scale's steps are ordered. This algorithm is recursive. Let x be the number of L's and y the number of s's. |
|
| |
|
| 1. If x and y are coprime (that is, they have no common factors other than 1), then go to step 2. If x and y are not coprime (that is, they share a common factor c, where c is the greatest common factor of x and y), then record that common factor c and repeat the algorithm recursively to produce the scale corresponding to x/c large steps and y/c small steps. Duplicate the scale produced this way c times, as this is a multi-period scale, then go to step 5. (If done correctly, this step will be performed exactly once, even across recursive calls.)
| | # If either x or y is equal to 1 (base cases): |
| | | ## If both x and y are equal to 1, then the final scale is "Ls". |
| 2. If either x or y is equal to 1, or both x and y are equal to 1, then proceed to step 3a, 3b, or 3c, depending on which situation is true. If not, proceed to either step 4a or 4b, depending on which situation is true.
| | ## If only x is equal to 1, then the final scale is L followed by y s's. |
| | | ## If only y is equal to 1, then the final scale is x L's followed by s. |
| 3a. If both x and y equal to 1, then the scale produced is exactly one L and exactly one s, or simply Ls. Proceed to step 5.
| | # If neither x nor y is equal to 1 (recursive cases): |
| | | ## Let k be the greatest common factor of x and y. |
| 3b. If only x = 1, then the scale produced consists of y s's followed by exactly one L. Proceed to step 5.
| | ## If x and y share a common factor k, where k is greater than 1, then recursively call this algorithm to find the scale for (x/k)L (y/k)s; the final scale will be (x/k)L (y/k)s duplicated k times. |
| | | ## If x and y don't share a common factor that is greater than 1 (if x and y are coprime), then: |
| 3c. If only y = 1, then the scale produced consists of x L's followed by exactly one s. Proceed to step 5.
| | ### Let m1 = min(x, y) and m2 = max(x, y). |
| | | ### Let z = m2 mod m1 and w = m1 - z. |
| 4a. If there are more large steps than small steps (that is, x > y), then the scale will consist of y groups. Of those groups, x mod y groups will contain ceil(x/y) large steps and exactly one small step, and y - (x mod y) groups will contain floor(x/y) large steps and exactly one small step. Record the production rules L -> LL...LLs (where the number of L's is ceil(x/y)) and s -> LL...LLs (where the number of L's is floor(x/y)). Repeat the algorithm recursively for the scale with (x mod y) large steps and (y - (x mod y)) small steps to produce an intermediate scale. Replace L and s in the intermediate scale according to the production rules produced earlier, then proceed to step 5.
| | ### Let prescale be the mos string for zL ws. Recursively call this algorithm to find the scale for zL ws; the final scale will be based on this. |
| | | ### If x > y, reverse the order of characters in the prescale. This is only needed if there are more L's than s's in the final scale. |
| 4b. If there are more small steps than large steps (that is, y > x), then the scale will consist of x groups. Of these groups, y mod x groups will contain exactly one large step and ceil(y/x) small steps, and x - (y mod x) groups will contain exactly one large step and floor(y/x) small steps. Record the production rules L -> ss...ssL (where the number of s's is ceil(y/x)) and s -> ss...ssL (where the number of s's is floor(y/x)). Repeat the algorithm recursively for the scale with (y mod x) large steps and (x - (y mod x)) small steps to produce an intermediate scale. Replace L and s in the intermediate scale according to the production rules produced earlier, then proceed to step 5.
| | ### To produce the final scale, the L's and s's of the prescale must be replaced with substrings consisting of L's and s's. Let u = ceil(m2/m1) and v = floor(m2/m1). |
| | | #### If x > y, every instance of an L in the prescale is replaced with one L and u s's, and every s replaced with one L and v s's. This produces the final scale in its brightest mode. |
| 5. If the algorithm was never called recursively, or the algorithm has reached this step after returning from its recursive calls, then the scale produced from the previous steps is the final scale, represented in its brightest mode if there are were L's than s's or the number of L's and s's were the same, or its darkest mode if ther were more s's than L's. If the algorithm was called as part of a recursive step, then the scale produced from the previous steps is an intermediate scale. Return the scale produced to when the algorithm was recursively called, and continue from that step.
| | #### If y > x, every instance of an L in the prescale is replaced with u L's and one s, and every s replaced with v L's and one s. This produces the final scale in its brightest mode. |
| | |
| (TODO: Examples)
| |
|
| |
|
| === Pseudocode === | | === Pseudocode === |
| This is the pseudocode for the algorithm described above. | | This is the pseudocode for the algorithm described above. (work-in-progress) |
| Pseudocode | | Pseudocode |
| | | |