StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POList of minimal pairs from a pair of lists
text
Body
copied!<p>Given two lists of integers, generate the shortest list of pairs where every value in both lists is present. The first of each pair must be a value from the first list, and the second of each pair must be a value from the second list. The first of each pair must be less than the second of the pair.</p> <p>A simple <code>zip</code> will not work if the lists are different lengths, or if the same integer exists at the same position in each list.</p> <pre><code>def gen_min_pairs(uplist, downlist): for pair in zip(uplist, downlist): yield pair </code></pre> <p>Here is what I can come up with so far:</p> <pre><code>def gen_min_pairs(uplist, downlist): up_gen = iter(uplist) down_gen = iter(downlist) last_up = None last_down = None while True: next_out = next(up_gen, last_up) next_down = next(down_gen, last_down) if (next_up == last_up and next_down == last_down): return while not next_up < next_down: next_down = next(down_gen, None) if next_down is None: return yield next_up, next_down last_up = next_up last_down = next_down </code></pre> <p>And here is a simple test routine:</p> <pre><code>if __name__ == '__main__': from pprint import pprint datalist = [ { 'up': [1,7,8], 'down': [6,7,13] }, { 'up': [1,13,15,16], 'down': [6,7,15] } ] for dates in datalist: min_pairs = [pair for pair in gen_min_pairs(dates['up'], dates['down'])] pprint(min_pairs) </code></pre> <p>The program produces the expect output for the first set of dates, but fails for the second.</p> <p>Expected:</p> <pre><code>[(1, 6), (7, 13), (8, 13)] [(1, 6), (1, 7), (13, 15)] </code></pre> <p>Actual:</p> <pre><code>[(1, 6), (7, 13), (8, 13)] [(1, 6), (13, 15)] </code></pre> <p>I think this can be done while only looking at each element of each list once, so in the complexity <code>O(len(up) + len(down))</code>. I think it depends on the number elements unique to each list.</p> <p>EDIT: I should add that we can expect these lists to be sorted with the smallest integer first.</p> <p>EDIT: <code>uplist</code> and <code>downlist</code> were just arbitrary names. Less confusing arbitrary ones might be <code>A</code> and <code>B</code>.</p> <p>Also, here is a more robust test routine:</p> <pre><code>from random import uniform, sample from pprint import pprint def random_sorted_sample(maxsize=6, pop=31): size = int(round(uniform(1,maxsize))) li = sample(xrange(1,pop), size) return sorted(li) if __name__ == '__main__': A = random_sorted_sample() B = random_sorted_sample() min_pairs = list(gen_min_pairs(A, B)) pprint(A) pprint(B) pprint(min_pairs) </code></pre> <p>This generates random realistic inputs, calculates the output, and displays all three lists. Here is an example of what a correct implementation would produce:</p> <pre><code>[11, 13] [1, 13, 28] [(11, 13), (13, 28)] [5, 15, 24, 25] [3, 13, 21, 22] [(5, 13), (15, 21), (15, 22)] [3, 28] [4, 6, 15, 16, 30] [(3, 4), (3, 6), (3, 15), (3, 16), (28, 30)] [2, 5, 20, 24, 26] [8, 12, 16, 21, 23, 28] [(2, 8), (5, 12), (5, 16), (20, 21), (20, 23), (24, 28), (26, 28)] [3, 4, 5, 6, 7] [1, 2] [] </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