Question: How can I efficiently remove all twins associated with each element of a given list?


I'm seeking an efficient solution to a particular problem. To illustrate, I'll provide a simplified example, though in practice, I'm handling lists with millions of elements.

Let's take the list, l: [1, 2, 3, 4, 5, 6, 7, 8]. Each element in this list has a corresponding twin. For instance, 1 has twins [4, 5], and 2 has twins [9, 12] (note that 12 is not in the original list, but that's not problematic). The complete list of twins is represented as t: [[4, 5], [9, 12], [6, 8], [1, 5], [1, 4], [3, 8], [13, 14, 17], [3, 6], [2, 12], [11, 12, 15]], and the twins are made available as they are needed.

The objective is to remove all twins starting from the first element of the list. Once a twin is removed, there's no need to check for twins for that particular element. For example, consider the first element, 1; the twins [4, 5] are removed, and there's no need to find the twins for those elements. The desired outcome would be the list [1, 2, 3, 7,10].

My solution utilizes a combination of a while loop and sets. However, it's painfully slow when dealing with lists larger than a few hundred thousand elements. 

Many thanks.  

Please Wait...