The smallest upravel (Q1193744)

An unravel of a sequence \(x\) is a bag of nonempty subsequences of \(x\) that when shuffled together can give back \(x\). For example, the sequence ``accompany'' can be unravelled into three lists ``acm'', ``an'', and ``copy''. The order of these lists is not important but duplications do matter; for example, ``peptet'' can be unravelled into two copies of ``pet''. Thus, an unravel is essentially a bag of sequences and not a list or set. An unravel is called an upravel if all its component sequences are ascending. Since each of ``acm'', ``an'', and ``copy'' are ascending, they give an upravel of ``accompany''. Each nonempty sequence has at least one upravel, namely the upravel consisting of just singleton sequences. However, of all possible upravels we want to determine one with the least number of elements. The problem was first posed by L.Meertens in September 1984, at a meeting of WG2.1 at Pont a Mousson, France. Subsequently, \textit{A. Kaldewaij} [Inf. Process. Lett. 21, 69 (1985; Zbl 0575.68074)] published a quite different solution. Kaldewaij's solution was based on a constructive proof of a specialisation of Dilworth's theorem: the size of a smallest upravel of \(x\) is equal to the length of the longest decreasing subsequence of \(x\). This fact can be combined with a well-known algorithm for finding the length of a longest decreasing subsequence in \(O(n\log n)\) steps to produce an algorithm for the smallest upravel with the same time complexity. Although Kaldewaij's method is a model of mathematical elegance and brevity, it is somewhat unsatisfactory from the perspective of a computing scientist interested in the principles of systematic algorithm design. The key notion, that of a longest decreasing sequence, is pulled out of a hat (the technical term is ``rabbit''). Our purpose here is to consider more direct approaches to the problem, including a rephrasing of Meertens' original derivation. In order to focus on the essential ideas, as well as keeping the presentation reasonably short, we omit many formal details.