3 ms·

Fun problem, at least abstractly. Here's a similar, maybe more basic approach for positive integers. It uses the idea at the beginning of the article to store n

by bo1024 9y ago

Fun problem, at least abstractly. Here's a similar, maybe more basic approach for positive integers. It uses the idea at the beginning of the article to store numbers in unary, to store the length of the number in unary ... recursively. The idea is to sort by ... the length of the length of the length of the number, then by the length of the length of the number, then by the length of the number, then by the number. First, imagine we store the number in the form aaaaaaaaaaa 92389210184 where the number of a's is equal to the length of the number. This encoding scheme works for the same reasons as discussed in the article. And it only takes 2*(length of original number)+1 characters. But now, we can do better by applying the same encoding scheme to the 'aaaaaaaaaaa'. That is, suppose the original number is 295 digits long. The number 295 is 3 digits long. So we store the number with 3 b's, as: bbb 295 109382388575782352353453.... OK, but what if we want to store a number that's 4,000,000,000 digits long? This would look like bbbbbbbbbb 4000000000 109382388575782352353453.... And that's a bit wasteful. If there are more than two b's, then we can recursively apply the encoding to the b's. There are 10 b's, and 10 has two digits, so we get cc 10 4000000000 109382388575782352353453.... And so on. (We won't ever have hard drives that can make use of letters e and above, so it can probably stop there.) So the encoding schemes look like a n # n is only one digit aa n # n is two digits b log10(n) n # log10(n) is one digit bb log10(n) n # log10(n) is two digits c log10(log10(n)) log10(n) n # log10(log10(n)) is one digit cc log10(log10(n)) log10(n) n # log10(log10(n)) is two digits d log10(log10(log10(n))) log10(log10(n)) log10(n) n ...

ahs1200 9y ago
Negative numbers?
- dbaupp 9y ago
  The same trick the article uses works.
rocqua 9y ago
Does this have a canonical form? It seems like the same number has multiple possible encodings that don't sort at the same place.
- bo1024 9y ago
  You'd definitely have to be more careful than I was in my post! But I think it should be possible to make it work via something like always using either one or two initial letters. The algorithm I'm thinking of is: 1. Given n, write aaaaaaa n where the number of a's is equal to the length of n. 2. If the number of a's is 1 or 2, stop. 3. Let n' be the number of a's. 4. Write bbbbb n' n where the number of b's is equal to the length of n'. 5. If the number of b's is 1 or 2, stop. 6. ...continue until the number of initial letters is 1 or 2. I think that algorithm is mostly well-defined and only produces one possible output for each input number. So let's see if I can give a good proof-ish argument that it sorts correctly. Suppose n <= m, then length(n) <= length(m). Case 1: If their lengths are equal, then in step 1, they are written as aaaaaaaaa n aaaaaaaaa m where the number of a's are the same. Now the rest of the algorithm is the same for both numbers, since they have the same number of a's, so they get written as the exact same prefix followed by the number. Since they have the same length, the smaller one sorts first. Case 2: Now suppose length(n) < length(m), and further suppose length(n) <= 2. Then in step 1, they are written as, for instance, a n aa m or something like aa n aaaa m Now any encoding of m in further steps will start with the letter b or greater, which sorts below "aa n". Case 3: Now suppose length(n) < length(m), but further suppose length(n) > 2. Then in step 1, they are written as aaaaaaaaa n aaaaaaaaaaa m Now n will sort before m as long as the encoding of a smaller string of a's sorts before the encoding of a longer string. Let n' = length(n) and m' = length(m). We know that n' < m' and we want to prove that the encoding of n' sorts before the encoding of m'. This is true recursively by the same 3-case argument as above, though I haven't really formalized it well here. For example, if length(n') = length(m'), then they both get written in the next step as bbbb n' n bbbb m' m which is just like Case 1 above. Otherwise, they get written something like b n' n bbb m' m which is just like Case 2 above. Otherwise, they get written bbbbb n' n bbbbbb m' m which is like Case 3 above, and requires us to recurse again.

by bo1024 9y ago

ahs1200 9y ago

Negative numbers?

dbaupp 9y ago
The same trick the article uses works.

rocqua 9y ago

Does this have a canonical form? It seems like the same number has multiple possible encodings that don't sort at the same place.

bo1024 9y ago
You'd definitely have to be more careful than I was in my post! But I think it should be possible to make it work via something like always using either one or two initial letters. The algorithm I'm thinking of is: 1. Given n, write aaaaaaa n where the number of a's is equal to the length of n. 2. If the number of a's is 1 or 2, stop. 3. Let n' be the number of a's. 4. Write bbbbb n' n where the number of b's is equal to the length of n'. 5. If the number of b's is 1 or 2, stop. 6. ...continue until the number of initial letters is 1 or 2. I think that algorithm is mostly well-defined and only produces one possible output for each input number. So let's see if I can give a good proof-ish argument that it sorts correctly. Suppose n <= m, then length(n) <= length(m). Case 1: If their lengths are equal, then in step 1, they are written as aaaaaaaaa n aaaaaaaaa m where the number of a's are the same. Now the rest of the algorithm is the same for both numbers, since they have the same number of a's, so they get written as the exact same prefix followed by the number. Since they have the same length, the smaller one sorts first. Case 2: Now suppose length(n) < length(m), and further suppose length(n) <= 2. Then in step 1, they are written as, for instance, a n aa m or something like aa n aaaa m Now any encoding of m in further steps will start with the letter b or greater, which sorts below "aa n". Case 3: Now suppose length(n) < length(m), but further suppose length(n) > 2. Then in step 1, they are written as aaaaaaaaa n aaaaaaaaaaa m Now n will sort before m as long as the encoding of a smaller string of a's sorts before the encoding of a longer string. Let n' = length(n) and m' = length(m). We know that n' < m' and we want to prove that the encoding of n' sorts before the encoding of m'. This is true recursively by the same 3-case argument as above, though I haven't really formalized it well here. For example, if length(n') = length(m'), then they both get written in the next step as bbbb n' n bbbb m' m which is just like Case 1 above. Otherwise, they get written something like b n' n bbb m' m which is just like Case 2 above. Otherwise, they get written bbbbb n' n bbbbbb m' m which is like Case 3 above, and requires us to recurse again.