Organizing list of tuples
<p>I have a list of tuples which I create dynamically.</p>

<p>The list appears as:</p>

<pre><code>List = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)]
</code></pre>

<p>Each tuple <code>(a, b)</code> of list represents the range of indexes from a certain table.</p>

<p>The ranges <code>(a, b) and (b, d)</code> is same in my situation as <code>(a, d)</code></p>

<p>I want to merge the tuples where the 2nd element matches the first of any other.</p>

<p>So, in the example above, I want to merge <code>(8, 10), (10,13)</code> to obtain <code>(8,13)</code> and remove <code>(8, 10), (10,13)</code></p>

<p><code>(19,25) and (25,30)</code> merge should yield <code>(19, 30)</code></p>

<p>I don't have a clue where to start. The tuples are non overlapping.</p>

<p>Edit: I have been trying to just avoid any kind of for loop as I have a pretty large list</p>

<p>If you need to take into account things like skovorodkin's example in the comment, </p>

<pre><code>[(1, 4), (4, 8), (8, 10)]
</code></pre>

<p>(or even more complex examples), then one way to do efficiently would be using graphs. </p>

<p>Say you create a digraph (possibly using <a href="https://networkx.github.io/" rel="nofollow"><code>networkx</code></a>), where each pair is a node, and there is an edge from <em>(a, b)</em> to node <em>(c, d)</em> if <em>b == c</em>. Now run <a href="https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.dag.topological_sort.html" rel="nofollow">topological sort</a>, iterate according to the order, and merge accordingly. You should take care to handle nodes with two (or more) outgoing edges properly.</p>

<hr>

<p>I realize your question states you'd like to avoid loops on account of the long list size. Conversely, for long lists, I doubt you'll find even an efficient linear time solution using list comprehension (or something like that). Note that you cannot sort the list in linear time, for example.</p>

<hr>

<p>Here is a possible implementation:</p>

<p>Say we start with</p>

<pre><code>l = [(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)]
</code></pre>

<p>It simplifies the following to remove duplicates, so let's do:</p>

<pre><code>l = list(set(l))
</code></pre>

<p>Now to build the digraph:</p>

<pre><code>import networkx as nx
import collections

g = nx.DiGraph()
</code></pre>

<p>The vertices are simply the pairs:</p>

<pre><code>g.add_nodes_from(l)
</code></pre>

<p>To build the edges, we need a dictionary:</p>

<pre><code>froms = collections.defaultdict(list)
for p in l:
    froms[p[0]].append(p)
</code></pre>

<p>Now we can add the edges:</p>

<pre><code>for p in l:
    for from_p in froms[p[1]]:
        g.add_edge(p, from_p)
</code></pre>

<p>Next two lines are unneeded - they're just here to show what the graph looks like at this point:</p>

<pre><code>&gt;&gt;&gt; g.nodes()
[(25, 30), (14, 16), (10, 13), (8, 10), (1, 4), (19, 25)]

&gt;&gt;&gt; g.edges()
[((8, 10), (10, 13)), ((19, 25), (25, 30))]
</code></pre>

<p>Now, let's sort the pairs by topological sort:</p>

<pre><code>l = nx.topological_sort(g)
</code></pre>

<p>Finally, here's the tricky part. The result will be a DAG. We have to to traverse things recursively, but remember what we visited already.</p>

<p>Let's create a dict of what we visited:</p>

<pre><code>visited = {p: False for p in l}
</code></pre>

<p>Now a recursive function, that given a node, returns the maximum range edge from any node reachable from it:</p>

<pre><code>def visit(p):
    neighbs = g.neighbors(p)
    if visited[p] or not neighbs:
        visited[p] = True
        return p[1]
    mx = max([visit(neighb_p) for neighb_p in neighbs])
    visited[p] = True
    return mx
</code></pre>

<p>We're all ready. Let's create a list for the final pairs:</p>

<pre><code>final_l = []
</code></pre>

<p>and visit all nodes:</p>

<pre><code>for p in l:
    if visited[p]:
        continue
    final_l.append((p[0], visit(p)))
</code></pre>

<p>Here's the final result:</p>

<pre><code>&gt;&gt;&gt; final_l
[(1, 4), (8, 13), (14, 16)]
</code></pre>

python algorithm list tuples