News for hackers. Stuff that matters.
Re:Sorting number strings numerically by bo1024 on Thursday September 07, 2017 @12:04PM (#15193068)
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
    ...
Re:Sorting number strings numerically by rocqua on Thursday September 07, 2017 @01:49PM (#15194131)
Does this have a canonical form? It seems like the same number has multiple possible encodings that don't sort at the same place.
Re:Sorting number strings numerically by bo1024 on Thursday September 07, 2017 @02:42PM (#15194633)
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.
Re:Sorting number strings numerically by ahs1200 on Thursday September 07, 2017 @12:40PM (#15193470)
Negative numbers?
Re:Sorting number strings numerically by dbaupp on Thursday September 07, 2017 @12:53PM (#15193633)
The same trick the article uses works.