Matching relative order in subsequence of fixed length - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T02:52:21Z https://cs.stackexchange.com/feeds/question/99090 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/99090 3 Matching relative order in subsequence of fixed length Jingjie YANG https://cs.stackexchange.com/users/63418 2018-10-25T15:09:40Z 2018-10-26T06:23:02Z <p>I encountered this problem from game development which I will formulate in a more formal way:</p> <blockquote> <p>Given a sequence <span class="math-container">$A = a_1, a_2, \dots, a_m$</span> and a permutation of <span class="math-container">$\{1, \dots, n\}$</span>, <span class="math-container">$B = b_1, b_2, \dots b_n$</span>, find all <span class="math-container">$i$</span> such that for all <span class="math-container">$1 \leq j \leq n$</span>, <span class="math-container">$a_{i + j}$</span> is the <span class="math-container">$b_j$</span>th smallest element of <span class="math-container">$a_{i + 1}, a_{i + 2}, \dots, a_{i + n}$</span>.</p> </blockquote> <p><strong>Example:</strong></p> <ul> <li><span class="math-container">$A = 6, 1, 3, 4, 5$</span></li> <li><span class="math-container">$B = 1, 2, 3$</span></li> <li><span class="math-container">$i = 1$</span>: <span class="math-container">$1, 3, 4$</span> matches the relative order of <span class="math-container">$1, 2, 3$</span></li> <li><span class="math-container">$i = 2$</span>: <span class="math-container">$3, 4, 5$</span> matches the relative order of <span class="math-container">$1, 2, 3$</span></li> </ul> <p>The brute force approach consists of sorting each subsequence of length <span class="math-container">$n$</span> and comparing the sorted indices to <span class="math-container">$B$</span>, and this is done <span class="math-container">$m - n + 1$</span> times, thus resulting in a time complexity of <span class="math-container">$\mathcal{O}(mn \log n)$</span>. </p> <p>I have only managed to improve this very slightly, by sorting only the first subsequence in <span class="math-container">$\mathcal{O}(n \log n)$</span> time and then removing <span class="math-container">$a_i$</span> and inserting <span class="math-container">$a_{i + n + 1}$</span> which both take <span class="math-container">$\mathcal{O}(n)$</span> time, resulting in a time complexity of <span class="math-container">$\mathcal{O}(n \log n + mn)$</span>.</p> <p>I do realise that my approaches are very rudimentary and there should exist a much more efficient algorithm that runs in less than <span class="math-container">$\mathcal{O}(m n)$</span> time. Unfortunately, I cannot think of any relevant algorithms that I know of, and searching online with how I described the problem have yet brought any useful resources.</p>