<p>By using the adversary method, the last generated time could be the previous object in the ordering of your preference. Therefore, in order to distinguish between any two numbers (and thus be able to order them) you would have to use information equivalent to the length of the full representation.</p>

<p>I believe that this question is related to issues in databases and relational algebra such as primary key selection. I don't think you need to refrain to pure information-theory arguments in order to solve this problem.</p>

CC BY-SA 3.0
2011-12-28T03:46:59.257Z
2011-12-29T02:51:30.407Z
2011-12-29T02:51:30.407Z
chazisop
<p>From a distance, it looks somewhat like this to me:  </p>

<p>Let there be a constant defined at the beginning, set to the real time clock value at program start.  </p>

<p>Include with each output generated, the difference between the value to be printed and this constant (in hex if you like), which actually is the unique value of time elapsed since program start.  </p>

<p>That should serve the purpose? This is not a generalized algorithm, though.</p>

CC BY-SA 3.0
2011-12-29T12:37:35.200Z
What's a "real time clock"?
Jeffε
CC BY-SA 3.0
2011-12-29T12:56:04.897Z
The system clock -- providing the system time. You could read it as "... set to system time at program start" in the sentence above.
Kris
CC BY-SA 3.0
2011-12-29T13:21:24.583Z
What's a "system clock"?  What is "system time"?  (Keep in mind that this is a forum for questions in theoretical computer science.  The standard theoretical model of computation does not have a system clock.  While it is possible to simulate such a clock with an instruction counter, the original question explicitly forbids counters.)
Jeffε
CC BY-SA 3.0
2014-03-29T05:51:02.913Z
@JɛﬀE See the answer by chazisop -- "I don't think you need to refrain to pure information-theory arguments in order to solve this problem."
Kris
CC BY-SA 3.0
2011-12-29T05:17:41.520Z
2011-12-29T05:17:41.520Z
Kris
<p>I wondered... </p>

<p>Lets say you have a machine, which sometimes prints out the time on a piece of paper in the following format: $$year-month-day-hours-minutes-seconds.$$</p>

<p>For example today it would print something like
$$11-12-27-20-03-58,$$
then maybe two and a half hour later
$$11-12-27-22-45-32,$$
and so on. You're investigating this machine and collect all the output it gives you. For convenience you write down a running number on the backs of these papers. This way you can sort and find the prints much faster. On the first ever print you wrote #1, on the second one you wrote #2, etc. When you reached #9999 you decided to switch to hexadecimal numbers to safe some space. </p>

<p>Then you have a better idea: You write a program to automatize this. Whenever the machine prints out a new time, the programm should write down which print it is in the above sense. There is only one problem: The program you'll write can't count, i.e. remember how many prints it has done. However, the program has access to the time printed on the paper. So it could just use the time itself to encode the order. But this is probably a waste of space. </p>

<p>Here the question: How can you <em>optimally</em> use the information you got to convert it into a sorted series, even if every time you only have access to the current print?</p>

<p>How can the solution to this specific problem be generalized? (i.e. not necessarily relying on this example, where the input is a time.)</p>

CC BY-SA 3.0
2011-12-28T03:12:37.550Z
The only information known is the current printed time?
Michael Blondin
CC BY-SA 3.0
2011-12-28T10:49:31.380Z
There is no nontrivial solution.  If you are not allowed *any* extra memory, then you cannot distinguish, even in principle, between a machine that spits out exactly one slip of paper and then dies (which requires NO bits to be written), and a machine that spits out one slip of paper every second for 10000 years (which requires as many bits as the times themselves).
Jeffε
CC BY-SA 3.0
2011-12-28T13:46:45.663Z
Just a (fool?) idea that works with time: whenever you receive a timestamp you can start a "private stopwatch", then, when a new timestamp arrives, subtract the stopwatch value from it and add 1 (and reset the stopwatch) ... this will help you to save some bits (suppose you receive 00'58", 01'30", 10'10" you print 58,59,131 instead of 58,130,1010). It can be generalized if you know the difference between the current and the last value received. Otherwise, without any memory "from the past", I think that all you can do is copy the data you receive.
Marzio De Biasi
CC BY-SA 3.0
2011-12-29T12:37:19.833Z
@Vor: Your strategy is identical to always writing down the previous time stamp plus 1.  Even if a private stopwatch is allowed by the model of computation (a bit of stretch in my opinion), the long-term savings are insignificant.
Jeffε
CC BY-SA 3.0
2011-12-29T13:33:35.937Z
@JɛﬀE Yes but could this machine handle 10000 years and more importantly how it handles it. Is it vulnerable to a millenium-like problem (because then we would have to use additional information to keep track of how many time the clock made a full period)? I hope Nikolaj can clarify this point or we can consider the case with no overlaps and then solve the more complicated one.
chazisop
CC BY-SA 3.0
2011-12-29T14:26:50.687Z
@JɛﬀE: I agree with you, the long-term savings are insignificant, and the "stopwatch" (a finite counter) is a weird way to calculate the last timestamp if we are not allowed to store anything from the past (and works only if the input is a time) ... but perhaps it can nicely represent a "battle for a bit" :-)
Marzio De Biasi
<ds.algorithms>
Efficiently converting an ascending sequence to a sorted sequence one at a time
Nikolaj-K
# Efficiently converting an ascending sequence to a sorted sequence one at a time

(Asked by: username_0 on 2011-12-28)

I wondered...

Lets say you have a machine, which sometimes prints out the time on a piece of paper in the following format: $$year-month-day-hours-minutes-seconds.$$

For example today it would print something like
$$11-12-27-20-03-58,$$
then maybe two and a half hour later
$$11-12-27-22-45-32,$$
and so on. You're investigating this machine and collect all the output it gives you. For convenience you write down a running number on the backs of these papers. This way you can sort and find the prints much faster. On the first ever print you wrote #1, on the second one you wrote #2, etc. When you reached #9999 you decided to switch to hexadecimal numbers to safe some space.

Then you have a better idea: You write a program to automatize this. Whenever the machine prints out a new time, the programm should write down which print it is in the above sense. There is only one problem: The program you'll write can't count, i.e. remember how many prints it has done. However, the program has access to the time printed on the paper. So it could just use the time itself to encode the order. But this is probably a waste of space.

Here the question: How can you *optimally* use the information you got to convert it into a sorted series, even if every time you only have access to the current print?

How can the solution to this specific problem be generalized? (i.e. not necessarily relying on this example, where the input is a time.)

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: The only information known is the current printed time?  
> **username_2**: There is no nontrivial solution.  If you are not allowed *any* extra memory, then you cannot distinguish, even in principle, between a machine that spits out exactly one slip of paper and then dies (which requires NO bits to be written), and a machine that spits out one slip of paper every second for 10000 years (which requires as many bits as the times themselves).  
> **username_3**: Just a (fool?) idea that works with time: whenever you receive a timestamp you can start a "private stopwatch", then, when a new timestamp arrives, subtract the stopwatch value from it and add 1 (and reset the stopwatch) ... this will help you to save some bits (suppose you receive 00'58", 01'30", 10'10" you print 58,59,131 instead of 58,130,1010). It can be generalized if you know the difference between the current and the last value received. Otherwise, without any memory "from the past", I think that all you can do is copy the data you receive.  
> **username_2**: @Vor: Your strategy is identical to always writing down the previous time stamp plus 1.  Even if a private stopwatch is allowed by the model of computation (a bit of stretch in my opinion), the long-term savings are insignificant.  
> **username_4**: @JɛﬀE Yes but could this machine handle 10000 years and more importantly how it handles it. Is it vulnerable to a millenium-like problem (because then we would have to use additional information to keep track of how many time the clock made a full period)? I hope Nikolaj can clarify this point or we can consider the case with no overlaps and then solve the more complicated one.  
> **username_3**: @JɛﬀE: I agree with you, the long-term savings are insignificant, and the "stopwatch" (a finite counter) is a weird way to calculate the last timestamp if we are not allowed to store anything from the past (and works only if the input is a time) ... but perhaps it can nicely represent a "battle for a bit" :-)  

---

## 2 answers

### Answer by username_4 on 2011-12-28. Score: 2

By using the adversary method, the last generated time could be the previous object in the ordering of your preference. Therefore, in order to distinguish between any two numbers (and thus be able to order them) you would have to use information equivalent to the length of the full representation.

I believe that this question is related to issues in databases and relational algebra such as primary key selection. I don't think you need to refrain to pure information-theory arguments in order to solve this problem.


---

### Answer by username_5 on 2011-12-29. Score: -1

From a distance, it looks somewhat like this to me:

Let there be a constant defined at the beginning, set to the real time clock value at program start.

Include with each output generated, the difference between the value to be printed and this constant (in hex if you like), which actually is the unique value of time elapsed since program start.

That should serve the purpose? This is not a generalized algorithm, though.

> **Comments:**
> **username_2**: What's a "real time clock"?  
> **username_5**: The system clock -- providing the system time. You could read it as "... set to system time at program start" in the sentence above.  
> **username_2**: What's a "system clock"?  What is "system time"?  (Keep in mind that this is a forum for questions in theoretical computer science.  The standard theoretical model of computation does not have a system clock.  While it is possible to simulate such a clock with an instruction counter, the original question explicitly forbids counters.)  
> **username_5**: @JɛﬀE See the answer by username_4 -- "I don't think you need to refrain to pure information-theory arguments in order to solve this problem."  

---

