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>You can use a dictionary to map the different end indices to the range ending at that index; then just iterate the list sorted by start index and merge the segments accordingly:</p>

<pre><code>def join_lists(lst):
    ending = {}  # will map end position to range
    for start, end in sorted(lst):  # iterate in sorted order
        if start in ending:
            ending[end] = (ending[start][0], end)  # merge
            del ending[start]  # remove old value
        else:
            ending[end] = (start, end)
    return list(ending.values())  # return remaining values from dict
</code></pre>

<p>Alternatively, as pointed out by <a href="http://stackoverflow.com/questions/39904161/organizing-list-of-tuples/39904621#comment67105721_39904621">Tomer W in comments</a>, you can do without the sorting, by iterating the list twice, making this solution take only linear time (<em>O(n)</em>) w.r.t. the length of the list.</p>

<pre><code>def join_lists(lst):
    ending = {}  # will map end position to range
    # first pass: add to dictionary
    for start, end in lst:
        ending[end] = (start, end)
    # second pass: lookup and merge
    for start, end in lst:
        if start in ending:
            ending[end] = (ending[start][0], end)
            del ending[start]
    # return remaining values from dict
    return list(ending.values())
</code></pre>

<p>Examples output, for both cases:</p>

<pre><code>&gt;&gt;&gt; join_lists([(1,4), (8,10), (19,25), (10,13), (14,16), (25,30)])
[(1, 4), (8, 13), (14, 16), (19, 30)]
&gt;&gt;&gt; join_lists(lst = [(1, 4), (4, 8), (8, 10)])
[(1, 10)]
</code></pre>

python algorithm list tuples