Here’s a brute-force approach (it might be easier to understand):
from itertools import chain
def condense(*lists):
# remember original positions
positions = {}
for pos, item in enumerate(chain(*lists)):
if item not in positions:
positions[item] = pos
# condense disregarding order
sets = condense_sets(map(set, lists))
# restore order
result = [sorted(s, key=positions.get) for s in sets]
return result if len(result) != 1 else result[0]
def condense_sets(sets):
result = []
for candidate in sets:
for current in result:
if candidate & current: # found overlap
current |= candidate # combine (merge sets)
# new items from candidate may create an overlap
# between current set and the remaining result sets
result = condense_sets(result) # merge such sets
break
else: # no common elements found (or result is empty)
result.append(candidate)
return result
Example
>>> condense([1,2,3], [10,5], [3,8,5])
[1, 2, 3, 10, 5, 8]
>>> a = [1,2,3]
>>> b = [3,4]
>>> i = [21,22]
>>> c = [88,7,8]
>>> e = [5,4]
>>> d = [3, 50]
>>> f = [8,9]
>>> g= [9,10]
>>> h = [20,21]
>>> condense(*[a,b,c,i,e,d,f,g,h,a,c,i]*1000)
[[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]
>>> condense([1], [2, 3, 2])
[[1], [2, 3]]
Performance comparison
condense_*()
functions are from the answers to this question. lst_OP
input list from the question (different size), lst_BK
– the test list from @Blckknght’s answer (different size). See the source.
Measurements show that solutions based on “disjoint sets” and “connected components of undirected graph” concepts perform similar on both types of input.
name time ratio comment
condense_hynekcer 5.79 msec 1.00 lst_OP
condense_hynekcer2 7.4 msec 1.28 lst_OP
condense_pillmuncher2 11.5 msec 1.99 lst_OP
condense_blckknght 16.8 msec 2.91 lst_OP
condense_jfs 26 msec 4.49 lst_OP
condense_BK 30.5 msec 5.28 lst_OP
condense_blckknght2 30.9 msec 5.34 lst_OP
condense_blckknght3 32.5 msec 5.62 lst_OP
name time ratio comment
condense_blckknght 964 usec 1.00 lst_BK
condense_blckknght2 1.41 msec 1.47 lst_BK
condense_blckknght3 1.46 msec 1.51 lst_BK
condense_hynekcer2 1.95 msec 2.03 lst_BK
condense_pillmuncher2 2.1 msec 2.18 lst_BK
condense_hynekcer 2.12 msec 2.20 lst_BK
condense_BK 3.39 msec 3.52 lst_BK
condense_jfs 544 msec 563.66 lst_BK
name time ratio comment
condense_hynekcer 6.86 msec 1.00 lst_rnd
condense_jfs 16.8 msec 2.44 lst_rnd
condense_blckknght 28.6 msec 4.16 lst_rnd
condense_blckknght2 56.1 msec 8.18 lst_rnd
condense_blckknght3 56.3 msec 8.21 lst_rnd
condense_BK 70.2 msec 10.23 lst_rnd
condense_pillmuncher2 324 msec 47.22 lst_rnd
condense_hynekcer2 334 msec 48.61 lst_rnd
To reproduce results clone gist and run measure-performance-condense-lists.py