Recursive structure of MOS scales: Difference between revisions
No edit summary |
|||
| Line 16: | Line 16: | ||
* There is a third special case where there is exactly one L and one s in the scale, producing "Ls" or "sL". Technically speaking, it's possible to reduce the previous two special cases even further into this special case. | * There is a third special case where there is exactly one L and one s in the scale, producing "Ls" or "sL". Technically speaking, it's possible to reduce the previous two special cases even further into this special case. | ||
In both case 1 and 2, the L's and s's are distributed | In both case 1 and 2, the L's and s's are distributed in a MOS way, but the chunks of L's and s's are arranged so that they too form a MOS. This can be demonstrated by reducing the larger chunks into L and the smaller chunks into s. This produces a new scale W that is also a moment-of-symmetry scale. This process can be repeated multiple times until the scale is reduced into one of the special cases. In case 3, it is possible to reduce a multi-period scale until it consists of a single unique MOS-like chunk repeated c times, where that chunk is one of the special cases. | ||
Note that in this reduction process, the order of L's and s's may reverse. This is normal. | Note that in this reduction process, the order of L's and s's may reverse. This is normal. | ||
| Line 37: | Line 37: | ||
==== Stepwise version ==== | ==== Stepwise version ==== | ||
This is the general algorithm for determining whether a binary scale | This is the general algorithm for determining whether a binary scale is a valid MOS. This version of the algorithm that uses the production rules in reverse: L -> Ls and s ->s; and L -> sL and s -> L. It is required to perform this on the string that represents the scale in its brightest mode. This algorithm is recursive. | ||
# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen: | # Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen: | ||
## If both x and y are equal to 1, then the scale is | ## If both x and y are equal to 1, then the scale is MOS. | ||
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is | ## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is MOS. If it's not the case that all of the substrings are identical or the substring is not MOS, then the scale is not MOS. | ||
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not | # If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not MOS. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not MOS. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another. | ||
# Split the string into a sequence of chunks as described: if there are more L's than s's (or if x > y), then each chunk will consist of at least one L followed by exactly one s; if instead there are more s's than L's (or y > x), then each chunk will consist of exactly one L followed by at least one s. Preserve the order of these chunks. | # Split the string into a sequence of chunks as described: if there are more L's than s's (or if x > y), then each chunk will consist of at least one L followed by exactly one s; if instead there are more s's than L's (or y > x), then each chunk will consist of exactly one L followed by at least one s. Preserve the order of these chunks. | ||
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not | # Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not MOS. If there are only two unique strings but their lengths differ by more than 1, then the scale is not MOS. | ||
# If there are more L's than s's, then for each chunk, replace all but the last two characters with s's, and replace the last two characters with a single L. This process represents L->sL and s->L. If there are more s's than L's, then for each chunk, replace only the first two characters with a single L. This process represents L->Ls and s->s, but reversed. The scale produced this way is the parent scale. | # If there are more L's than s's, then for each chunk, replace all but the last two characters with s's, and replace the last two characters with a single L. This process represents L->sL and s->L. If there are more s's than L's, then for each chunk, replace only the first two characters with a single L. This process represents L->Ls and s->s, but reversed. The scale produced this way is the parent scale. | ||
# Repeat the algorithm recursively on the parent scale. If that scale is | # Repeat the algorithm recursively on the parent scale. If that scale is MOS, then the original scale is MOS. | ||
==== Chunking version ==== | ==== Chunking version ==== | ||
This is the general algorithm for determining whether a binary scale is | This is the general algorithm for determining whether a binary scale is MOS (that is, it is a valid MOS). This version of the algorithm reduces entire chunks into L's and s's based on the size of the chunks. It is recommended, but not required, to perform this on the string representing the scale in either its brightest or darkest mode. This algorithm is recursive. | ||
# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen: | # Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen: | ||
## If either x or y is equal to 1, or both x and y are equal to 1, then the scale is | ## If either x or y is equal to 1, or both x and y are equal to 1, then the scale is MOS. | ||
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is | ## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is MOS. If it's not the case that all of the substrings are identical or the substring is not MOS, then the scale is not MOS. | ||
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not | # If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not MOS. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not MOS. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another. | ||
# Split the string into a sequence of chunks, not by splitting the strings into chunks that contain L's and s's, but AT the character that appears the least. Because every chunk contains at least one L and at least one s, removing the character that appears the least will not make any difference to how the chunks are ordered in terms of size. If there are more L's than s's, then there should be exactly y chunks consisting of only L's, and if there are more s's than L's, then there should be exactly x chunks consisting of only s's. If there is exactly one more string than expected, this may be because the string was in a mode that split one of the chunks into two; in this case, combine the first and last chunks in the sequence back into one chunk to get the correct number of chunks. | # Split the string into a sequence of chunks, not by splitting the strings into chunks that contain L's and s's, but AT the character that appears the least. Because every chunk contains at least one L and at least one s, removing the character that appears the least will not make any difference to how the chunks are ordered in terms of size. If there are more L's than s's, then there should be exactly y chunks consisting of only L's, and if there are more s's than L's, then there should be exactly x chunks consisting of only s's. If there is exactly one more string than expected, this may be because the string was in a mode that split one of the chunks into two; in this case, combine the first and last chunks in the sequence back into one chunk to get the correct number of chunks. | ||
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not | # Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not MOS. If there are only two unique strings but their lengths differ by more than 1, then the scale is not MOS. | ||
# Produce a new scale consisting of L's and s's, based on the sequence of tokenized strings, as this will be the progenitor scale of the original; in the sequence, every instance of the larger string corresponds to an L in the progenitor scale, and every instance of the smaller string corresponds to an s in that scale. Call this algorithm recursively on that scale to determine whether that scale is also | # Produce a new scale consisting of L's and s's, based on the sequence of tokenized strings, as this will be the progenitor scale of the original; in the sequence, every instance of the larger string corresponds to an L in the progenitor scale, and every instance of the smaller string corresponds to an s in that scale. Call this algorithm recursively on that scale to determine whether that scale is also MOS. If that scale is MOS, then the original scale is MOS. Otherwise, the scale is not MOS. | ||
=== Pseudocode === | === Pseudocode === | ||
This is the pseudocode for the chunking operation described above. | This is the pseudocode for the chunking operation described above. | ||
VeridyMOSScale(string scale : scale encodes an arbitrary scale of only L's and s's) returns TRUE or FALSE { | |||
integer x = 0; | integer x = 0; | ||
| Line 97: | Line 97: | ||
} else { | } else { | ||
string subscale = set.beginning_of_set | string subscale = set.beginning_of_set | ||
return | return VeridyMOSScale(subscale) | ||
} | } | ||
} | } | ||
| Line 153: | Line 153: | ||
subscale += "L" | subscale += "L" | ||
return | return VeridyMOSScale(subscale) | ||
} | } | ||
} | } | ||
| Line 177: | Line 177: | ||
=== Counterexamples === | === Counterexamples === | ||
LLLLsLs. This produces two unique chunks of LLLLs and Ls. However, the two chunks differ in size by two L's, and it is not | LLLLsLs. This produces two unique chunks of LLLLs and Ls. However, the two chunks differ in size by two L's, and it is not MOS. | ||
LLLLLss. This produces one chunk of LLLLLs. The lone s at the end can be considered a chunk consisting of zero L's and one s. Since the two chunks differ in size by 5 L's, this is not | LLLLLss. This produces one chunk of LLLLLs. The lone s at the end can be considered a chunk consisting of zero L's and one s. Since the two chunks differ in size by 5 L's, this is not MOS. | ||
LsssLsssL. The quantity of L's and s's are coprime, sharing a common factor of 3. However, dividing the scale into three equal-sized chunks shows that all three chunks are different (Lss, sLs, and ssL), so this is not | LsssLsssL. The quantity of L's and s's are coprime, sharing a common factor of 3. However, dividing the scale into three equal-sized chunks shows that all three chunks are different (Lss, sLs, and ssL), so this is not MOS. | ||
LLsLLLsLLLLs. This produces three unique chunks of LLs, LLLs, and LLLLs. This is not | LLsLLLsLLLLs. This produces three unique chunks of LLs, LLLs, and LLLLs. This is not MOS. | ||
== Finding the MOS pattern from xL ys == | == Finding the MOS pattern from xL ys == | ||