Saturday, November 29, 2014

Regarding Non-Alphabetical Ordering of Reduced Fractions as Strings

I ran across a programming problem a while back, and I've been meaning to post about the consequences of it.  There is a situation in which there are fractions that are represented as strings and that, by default, sort alphabetically.  The representations were immutable, but were usually reduced, so an ordering flag had to be added that would apply before the alphabetization.  I'll try to describe the problem mathematically below. 

Let F(n) be the set of fractions m/n such that m,n \in \!\, \mathbb{Z} \!\,, n > 1, n is not prime, 0 < m < n. 
Note:  If n were prime, then the solution would be trivial, since the fractions cannot be reduced, and therefore the proper order and alphabetical order would be the same.   
Assume that either (1) we use a high enough base that n is always a single character, or (2) every string representation of the fraction m/n, for every value of m, is equally and sufficiently 0-padded in both the numerator and the denominator.  (For an example of (2):  If n=10, then 9/10 would be "09/10", and 8/10=4/5 would be "04/05".)  For a given m, what is the minimum number of ordering flags such that, if each fraction m/n is associated with one, then sorted first by flag and then alphabetically, the fractions, even reduced, would be in ascending order? 

An Example: 
Let n = 8. 
F(n) = {1/8, 2/8, 3/8, 4/8, 5/8, 6/8, 7/8} = {1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8}. 
If sorted alphabetically, then these fractions would come out as "1/2, 1/4, 1/8, 3/4, 3/8, 5/8, 7/8". 
Assume that 3 flags is sufficient.  Call them "a", "b", and "c".  Clearly, 1/8 will need "a", 1/4 will need "b", and 1/2 will need "c".  Similarly, 3/4 will need either "a" or "b", and 3/8 will need either "b" or "c", but they cannot both take "b". 
For brevity and clarity, I will simply tack the flag on the front of the fraction, so that alphabetical order will put them in the proper order.  One valid association, then, produces "a1/8, b1/4, b3/8, c1/4, c5/8, c3/4, c7/8".  (In fact, I just realized that this is the only valid association on 3 flags, but I'll leave this as an exercise.)  
2 flags is not sufficient for this set:  If any {1/2, 1/4}, {1/4, 1/8}, or {1/2, 1/8} get the same flag, then they will resolve in the wrong order. 

When looking at the set, reduced, the minimum  number of flags is at least the largest number of common numerators (3, in the above example, as 3 of the reduced fractions had 1 as their numerator).  However, is there a good way to determine this purely from looking at n? 

Note:  I've also determined that 3 flags is sufficient when n=9, when n=10, and when n=6.  Demonstration of this is left as an exercise. 

Another example: 
Let n = 4. 
F(n) = {1/4, 2/4, 3/4} = {1/4, 1/2, 3/4}. 
2 flags is sufficient:  "a" must go with 1/4 and "b" with 1/2 (and 3/4), sorting them as "a1/4, b1/2, b3/4". 

Note:  In any case where 1 flag is sufficient, the solution is trivial.  That is, flagging is unnecessary. 

Conjecture:  The minimum number of flags needed to sort the reduced fractions alphabetically is x, where x is one less than the number of factors (prime or otherwise) of n. 

An example that attempts to exercise the conjecture: 
Let n = 12. 
Let H(n) be the set of factors of n.  For n=12, H(12) = {1, 2, 3, 4, 6, 12}.  The size of H is 6, so x=5. 
F(12) = {1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12} = {1/12, 1/6, 1/4, 3/4, 5/12, 1/2, 7/12, 2/3, 3/4, 5/6, 11/12}. 
This resolves as:  "01/02, 01/03, 01/04, 01/06, 01/12, 02/03, 03/04, 05/06, 05/12, 07/12, 11/12". 
Let us try to minimally alphabetize it: 
a01/12, b01/06, c01/04, d01/03, d05/12, e01/02, e07/12, f02/03, f03/04, f05/06, f11/12. 
5 flags was insufficient, as I had to go to 6 to put 2/3 after 7/12, so the conjecture is incorrect. 



Well, that's all for now.  I might revisit this problem at a later date.  We'll see. 

No comments: