EDITING ERRORS FROM A SUPPOSEDLY SORTED LIST.

An algorithm has been developed to solve the following problem: an ordered list may contain errors (i. e. items which violate the ordering of the list). Specify which items are errors in such a way that the list of non-error items is as long as possible. The problem may be restated as follows: sort a list by deleting as few items as necessary (exchange is not permitted). Since unbounded 'lookahead' is required to solve this problem, the algorithm requires on the order of n! comparisons, where n is the length of the list. The author has implemented the algorithm as a recursive PASCAL procedure.