Off the top of my head I'd do this. It should have good computational complexity (hash table) though as a general pattern-based method it is unlikely to be as fast a a numeric or compiled approach:
Module[{f},
f[{x_, _}] := (f[{_, x}] = False; True);
Select[testcase, f]
]
{{1, 2}, {1, 3}, {3, 4}, {4, 9}, {7, 5}}
It does have the advantage of being easy to apply to a series of lists: just omit the Module
.
I am assuming you have already filtered verbatim duplicates with DeleteDuplicates[testcase]
beforehand.
The code above was written in haste, without considering optimizations. After seeing belisarius's suggestion I propose this:
Module[{f, g},
g[_] = True;
f[{x_, _}] := (g[x] = False; True);
Cases[testcase, {_, _?g}?f]
]
{{1, 2}, {1, 3}, {3, 4}, {4, 9}, {7, 5}}
Timings:
big = DeleteDuplicates @ RandomInteger[999, {50000, 2}];
Module[{f},
f[{x_, _}] := (f[{_, x}] = False; True);
Select[big, f]
] // Length // Timing
{3.681, 4001}
Module[{f, g},
g[_] = True;
f[{x_, _}] := (g[x] = False; True);
Cases[big, {_, _?g}?f]
] // Length // Timing
{0.031, 4001}
I expect that this can be improved further, but I'm out of time. I'd start by trying "DefinitionsReordering" -> "None"
as done here.
Two more variations that are not as fast, but I like the style (the first one is pretty close):
Module[{g}, Cases[testcase, {x_, Except[_?g]} /; (g[x] = True)]]
Module[{g}, DeleteCases[testcase, {_, _?g} | {x_ /; (g[x] = True;), _}]]
{{1, 2}, {1, 3}, {3, 4}, {4, 9}, {7, 5}}
{{1, 2}, {1, 3}, {3, 4}, {4, 9}, {7, 5}}