On Stackoverflow, user asked a question about a data structure that would allow to keep an ordering for a set of items, with the condition of limited memory and only one item can be modified at a single operation. My feeling is that such an algorithm does NOT exist, but have no clue how to prove that.
First I tried to formalize the OPs requirements on the algorithm:
- The data structure keeps an order of given item set, i.e. one of
- Now the hard part comes. Not sure how to formalize that single item modification. We perhaps need to assume that the data structure keeps one of
O(n)possible values for each item. This matches both the numbering algorithms linked list algorithms mentioned in the OPs question, and many more (tree data structures etc.).
- Then say we have function
f(data structure)that will return the order (permutation) of all the items.
- Then suppose we have an operation which is a function
data_structure_after = op(data_structure_before)that will just change the position of one existing item relatively to the other items. During the operation, only value of one item can be changed.
We want to prove that such algorithm doesn't exist.
I got totally stuck here. It is totally clear why the numbering solution in the OPs question will not work, because it will break if you for example have items A, B, and C and keep putting the last item between the first two. It is also clear that linked list solution will break on the single item modifictaion requirement. But to prove non-existence, we must use much more general approach!
Maybe somehow start from the fact that
O(n^n) input values and
n! output values, and during each operation input values can only change for one item, thus
O(n) possible changes, has to produce
n changes at the output, so if we imagine this as a graph we have limitations of the number of edges going from each vertex... maybe use graph theory here. Then construct some infinite row of operations as a contra example that will either break on the single item modification requirement (like the linked list solution) or on the
O(n) requirement for the set of item values (like the numbering solution).
This was the basic idea but I am totally clueless how to actually perform the proof.