StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Algorithm: </p> <ol> <li>get all indexes into the inputArray of all queryArray values</li> <li>order them ascending by index</li> <li>using each index (x) as a starting point find the first higher index (y) such that the segment inputArray[x-y] contains all queryArray values</li> <li>keep only those segments that have the queryArray items in order</li> <li>order the segments by their lengths, ascending</li> </ol> <p>c# implementation:</p> <p>First get all indexes into the inputArray of all queryArray values and order them ascending by index.</p> <pre><code>public static int[] SmallestWindow(int[] inputArray, int[] queryArray) { var indexed = queryArray .SelectMany(x => inputArray .Select((y, i) => new { Value = y, Index = i }) .Where(y => y.Value == x)) .OrderBy(x => x.Index) .ToList(); </code></pre> <p>Next, using each index (x) as a starting point find the first higher index (y) such that the segment inputArray[x-y] contains all queryArray values.</p> <pre><code> var segments = indexed .Select(x => { var unique = new HashSet<int>(); return new { Item = x, Followers = indexed .Where(y => y.Index >= x.Index) .TakeWhile(y => unique.Count != queryArray.Length) .Select(y => { unique.Add(y.Value); return y; }) .ToList(), IsComplete = unique.Count == queryArray.Length }; }) .Where(x => x.IsComplete); </code></pre> <p>Now keep only those segments that have the queryArray items in order.</p> <pre><code> var queryIndexed = segments .Select(x => x.Followers.Select(y => new { QIndex = Array.IndexOf(queryArray, y.Value), y.Index, y.Value }).ToArray()); var queryOrdered = queryIndexed .Where(item => { var qindex = item.Select(x => x.QIndex).ToList(); bool changed; do { changed = false; for (int i = 1; i < qindex.Count; i++) { if (qindex[i] <= qindex[i - 1]) { qindex.RemoveAt(i); changed = true; } } } while (changed); return qindex.Count == queryArray.Length; }); </code></pre> <p>Finally, order the segments by their lengths, ascending. The first segment in the result is the smallest window into inputArray that contains all queryArray values in the order of queryArray.</p> <pre><code> var result = queryOrdered .Select(x => new[] { x.First().Index, x.Last().Index }) .OrderBy(x => x[1] - x[0]); var best = result.FirstOrDefault(); return best; } </code></pre> <p>test it with</p> <pre><code>public void Test() { var inputArray = new[] { 2, 1, 5, 6, 8, 1, 8, 6, 2, 9, 2, 9, 1, 2 }; var queryArray = new[] { 6, 1, 2 }; var result = SmallestWindow(inputArray, queryArray); if (result == null) { Console.WriteLine("no matching window"); } else { Console.WriteLine("Smallest window is indexes " + result[0] + " to " + result[1]); } } </code></pre> <p>output:</p> <pre><code>Smallest window is indexes 3 to 8 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload