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:

  1. The data structure keeps an order of given item set, i.e. one of n! permutations.
  2. 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.).
  3. Then say we have function f(data structure) that will return the order (permutation) of all the items.
  4. 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 f has 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.

  • $\begingroup$ Sorry I don't know which tags to put here. $\endgroup$ – Tomas Jan 7 '14 at 23:44
  • $\begingroup$ I think he should ask this question here, himself, if at all. $\endgroup$ – Ivarpoiss Jan 8 '14 at 16:22
  • $\begingroup$ @Ivarpoiss it's not relevant who is asking, only the question itself. If something needs to be clarified then please ask. $\endgroup$ – Tomas Jan 8 '14 at 16:30
  • $\begingroup$ I'm far from competent to answer this and proofs are the most alien concept for me, but my guess is, that in theory there does exist such algorithm, but proving anything here whould require far too much effort for anyone who doesn't have a much personal interest in this specific question. PS. this question would also relate to group theory. $\endgroup$ – Ivarpoiss Jan 8 '14 at 16:45
  • $\begingroup$ And such high level constraints like the actual number of actual records updated would also become quite irrelevant in the process. $\endgroup$ – Ivarpoiss Jan 8 '14 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.