# Replace list of list with "condensed" list of list while maintaining order

I have a list of list as in the code I attached. I want to link each sub list if there are any common values. I then want to replace the list of list with a condensed list of list. **Examples:** if I have a list [[1,2,3],[3,4]] I want [1,2,3,4]. If I have [[4,3],[1,2,3]] I want [4,3,1,2]. If I have [[1,2,3],[a,b],[3,4],[b,c]] I want [[1,2,3,4],[a,b,c]] or [[a,b,c],[1,2,3,4]] I don't care which one.

I am almost there...

My problem is when I have a case like [[1,2,3],[10,5],[3,8,5]] I want [1,2,3,10,5,8] but with my current code I get [1,2,3,8,10,5]

Here is my code:

import itertools 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] lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000 #I have a lot of list but not very many different lists def any_overlap(a, b): sb = set(b) return any(itertools.imap(sb.__contains__, a)) def find_uniq(lst): ''' return the uniq parts of lst''' seen = set() seen_add = seen.add return [ x for x in lst if x not in seen and not seen_add(x)] def overlap_inlist(o_lst, lstoflst): ''' Search for overlap, using "any_overlap", of a list( o_lst) in a list of lists (lstoflst). If there is overlap add the uniq part of the found list to the search list, and keep track of where that list was found ''' used_lst =[ ] n_lst =[ ] for lst_num, each_lst in enumerate(lstoflst): if any_overlap(o_lst,each_lst): n_lst.extend(each_lst) used_lst.append(lst_num) n_lst= find_uniq(n_lst) return n_lst, used_lst def comb_list(lst): ''' For each list in a list of list find all the overlaps using 'ovelap_inlist'. Update the list each time to delete the found lists. Return the final combined list. ''' for updated_lst in lst: n_lst, used_lst = overlap_inlist(updated_lst,lst) lst[:] = [x for i,x in enumerate(lst) if i not in used_lst] lst.insert(0,n_lst) return lst comb_lst = comb_list(lst) print comb_lst

The out put from this script is:

[[88, 7, 8, 9, 10], [1, 2, 3, 4, 50, 5], [21, 22, 20]]

I want it so the key are in the original order like:

[[88, 7, 8, 9, 10], [1, 2, 3, 4, 5, 50,], [21, 22, 20]]

The **5 and 50 are switched** in new lst[2]

I am somewhat new to python. I would appreciate any solutions to the problem or comments on my current code. I am not a computer scientists, I imagine there may be some kind of algorithm that does this quickly( maybe from set theory? ). If there is such an algorithm please point me to the right direction.

I may be making this way more complicated then it is... Thank you!!

## Answers

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

Here's my approach. It uses the concept of a "disjoint set" to first identify which sublists overlap with each other, then it joins them together, eliminating duplicates.

from collections import OrderedDict def disjoint_set_find(djs, node): # disjoint set find, with path compression if node not in djs: # base case, node is a root of a set return node djs[node] = disjoint_set_find(djs, djs[node]) # recurse, caching results return djs[node] def disjoint_set_union(djs, first, second): first = disjoint_set_find(djs, first) # find root of first set second = disjoint_set_find(djs, second) # and of second set if first < second: # make smaller root the root of the new combined set djs[second] = first elif second < first: djs[first] = second # deliberately ignore the case where first == second (same set) def condenseBK(*master_list): values = OrderedDict() # maps values to the first sublist containing them overlaps = {} # maps sublist indexes to each other to form a disjoint set for i, sublist in enumerate(master_list): for v in sublist: if v not in values: # no overlap, so just store value values[v] = i else: # overlap detected, do a disjoint set union disjoint_set_union(overlaps, values[v], i) output = [] # results output_map = {} # map from original indexes to output indexes for v, i, in values.items(): # iterate over values in order root = disjoint_set_find(overlaps, i) if root not in output_map: output_map[i] = len(output) output.append([]) # create new output sublists as necessary output[output_map[root]].append(v) return output

Sample output:

>>> a = [1,2,3] >>> b = [3,4] >>> c = [88,7,8] >>> d = [3, 50] >>> e = [5,4] >>> f = [8,9] >>> g = [9,10] >>> h = [20,21] >>> i = [21,22] >>> lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000 >>> condenseBK(*lst) [[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

An explanation of the algorithm:

By request, here's an explanation for how my code works.

The first two functions implement the find and union operations of a disjoint set. The data structure is implemented with a dictionary mapping nodes to their parent nodes. Any node that is not a key of the dictionary is the root of a set. The find operation returns the root node of the set containing a given node. To help performance a bit, I've implemented "path compression", which reduces the number of recursive steps needed over time. The union operation combines the sets containing its arguments first and second.

The main condense function has two parts. First, it sets up a couple of data structures, then it uses them to build the output.

values is an OrderedDictionary that maps from each value to the index of the first sublist it is contained in. The order each value is added is used to produce the output in the correct order.

overlaps is the dictionary used as for the disjoint set. Its nodes are the integer indexes of overlapping sublists.

The first loops fill up those two data structures. They loop over the sublists and their contents. If a value has not been seen before, it is added to the values dictionary. If it has been seen, the current sublist is overlapping a previous sublist containing that value.

To resolve the overlap, the code does a union of the disjoint sets that contain the two sublists.

The output is built in the output list. Because there are likely to be fewer output sublists than there were in the input, we need an additional dictionary to map between the old indexes (from the input) to the new indexes that apply to the output list.

To fill up the output list, we iterate over the values, which happens in the order they were added thanks to using the OrderedDict class. Using the disjoint set, it can combine the overlapping lists correctly.

This algorithm has very good performance when there are a lot of lists to be processed that don't overlap immediately. For instance, this set of 200 three-element lists ultimately all overlaps, but you only start seeing the overlaps appear after the first 100 have been processed:

lst2 = [list(range(4*i, 4*(i+1)-1)) for i in range(100)] + \ [list(range(4*i+2, 4*(i+1)+1)) for i in range(100)]

I am **sure** there is a cleaner way to do this but I started down a certain path and did what I had to to make it work without any refactoring.

lookup = {} out = [] index = 0 for grp in lst: keys = [lookup.get(num, None) for num in grp] keys = [key for key in keys if key is not None] if len(keys): if len(set(keys)) != 1: for num in grp: out[keys[0]].append(num) seen = set() keys = [key for key in keys if key not in seen and not seen.add(key)] for key in keys[1:]: out[keys[0]].extend(out[key]) del out[key] seen = set() out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)] else: for num in grp: lookup[num] = keys[0] out[keys[0]].extend(grp) seen = set() out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)] else: out.append(grp) for num in grp: lookup[num] = index index += 1 print out

Thanks to @Steven for the list reduction technique with the set.

**OUTPUT**

[[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

Your problem is essentially a graph theoretic one, the problem of connected components, with an added requirement regarding the order of the elements of each component.

In your program, the set of all lists forms an undirected graph, where each list is a node in the graph. We say two lists are connected directly if they have common elements, and connected indirectly, if there exists a third list to which both are connected, either directly or indirectly. Given e.g. three lists [a, b], [b, c] and [c, d], then [a, b] and [b, c] are connected directly, as well as [b, c] and [c, d], but [a, b] and [c, d] are connected indirectly, since while they don't share common elements, they both share elements with the same list [b, c].

A group of nodes is a connected component if all nodes in the group are connected (directly or indirectly) and no other node in the graph is connected to any node in the group.

There is a fairly simple linear time algorithm that generates all connected components in an undirected graph. Using that, we can define a function that generates all lists of condensed disjoint lists, while keeping the order of their elements:

from itertools import imap, combinations_with_replacement from collections import defaultdict def connected_components(edges): neighbors = defaultdict(set) for a, b in edges: neighbors[a].add(b) neighbors[b].add(a) seen = set() def component(node, neighbors=neighbors, seen=seen, see=seen.add): unseen = set([node]) next_unseen = unseen.pop while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen yield node for node in neighbors: if node not in seen: yield component(node) def condense(lists): tuples = combinations_with_replacement(enumerate(imap(tuple, lists)), 2) overlapping = ((a, b) for a, b in tuples if not set(a[1]).isdisjoint(b[1])) seen = set() see = seen.add for component in connected_components(overlapping): yield [item for each in sorted(component) for item in each[1] if not (item in seen or see(item))] print list(condense([[1, 2, 3], [10, 5], [3, 8, 5], [9]])) print list(condense([[1, 2, 3], [5, 6], [3, 4], [6, 7]]))

Result:

[[1, 2, 3, 10, 5, 8], [9]] [[5, 6, 7], [1, 2, 3, 4]]

Time complexity of condense() is quadratic, since every list must be tested against every other list to find out if they have common elements. Therefore, the performance is awful. Can we improve it somehow? Yes.

Two lists are connected directly if they have common elements. We can turn this relationship around: two elements are connected directly if they belong to the same list, and connected indirectly if there exists a third element that is connected (directly or indirectly) to both of them. Given e.g. two lists [a, b] and [b, c], then a and b are connected directly, as well as b and c, and therefore a and c are connected indirectly. If we also adapt J.F.Sebastians idea of storing the position of each element's first occurrence, we can implement it like so:

def condense(lists): neighbors = defaultdict(set) positions = {} position = 0 for each in lists: for item in each: neighbors[item].update(each) if item not in positions: positions[item] = position position += 1 seen = set() def component(node, neighbors=neighbors, seen=seen, see=seen.add): unseen = set([node]) next_unseen = unseen.pop while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen yield node for node in neighbors: if node not in seen: yield sorted(component(node), key=positions.get)

It still uses the connected components algorithm, but this time we view elements as connected, not lists. The results are the same as before, but since time complexity is now linear, it runs much faster.

I tried to write a **fast and readable solution**. It is never much slower than other solutions, if I know, but can be sometimes much faster because it is additionally optimized for longer sublist or for many sublists that are subset of any yet existing group. (This is motivated by text of the question "I have a lot of list but not very many different lists.") The code uses less memory only for condensed data that can be much less than the original data. It can work e.g. with a generator collecting data from a realtime process. The estimate of complexity is O(n log n). I think that no algorithm that uses sorting can be of linear complexity.

def condense(lists): groups = {} # items divided into groups {id(the_set): the_set,...} members = {} # mapping from item to group positions = {} # mapping from item to sequential ordering iposition = 0 # counter for positions for sublist in lists: if not sublist or members.get(sublist[0], set()).issuperset(sublist): continue # speed-up condition if all is from one group common = set([x for x in sublist if x in members]) if common: # any common group can be a destination for merge dst_group = members[common.pop()] common = common - dst_group # are more groups common for sublist? while common: grp = members[common.pop()] if len(grp) > len(dst_group): # merge shorter into longer grp grp, dst_group = dst_group, grp dst_group.update(grp) for item in grp: members[item] = dst_group del groups[id(grp)] common = common - dst_group else: # or create a new group if nothing common dst_group = set() groups[id(dst_group)] = dst_group newitems = [] for item in sublist: # merge also new items if item not in positions: positions[item] = iposition iposition += 1 newitems.append(item) members[item] = dst_group dst_group.update(newitems) return [sorted(x, key=positions.get) for x in groups.values()]

It is faster than pillmuncher2 for subslists longer than approximately 8 items because it can work on more items together. It is also very fast for lists with many similar sublists or many sublists that are subset of any yet existing group. It is faster by 25% over pillmuncher2 for lst_OP, however slower by 15% for lst_BK.

An example of test data with long sublists is [list(range(30)) + [-i] for i in range(100)].

I intentionally wrote "common = common - dst_group" instead of using the set operator -= or "set.difference_update", because the updade in-place is not effective if the set on the right side is much bigger then on the left side.

**Modified pillmuncher's solution** for easier readability. The modification is a little slower than the original due to replacing a generator by list.append. Probably the most readable fast solution.

# Modified pillmuncher's solution from collections import defaultdict def condense(lists): neighbors = defaultdict(set) # mapping from items to sublists positions = {} # mapping from items to sequential ordering position = 0 for each in lists: for item in each: neighbors[item].update(each) if item not in positions: positions[item] = position position += 1 seen = set() see = seen.add for node in neighbors: if node not in seen: unseen = set([node]) # this is a "todo" set next_unseen = unseen.pop # method alias, not called now group = [] # collects the output while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen group.append(node) yield sorted(group, key=positions.get)

class List(list): pass rv = dict() def condense_step(): """find and merge one overlapping pair in rv""" for i, iv in rv.items(): for j, jv in rv.items(): if i != j and i.intersection(j): m = i.union(j) del rv[i] del rv[j] rv.setdefault(m, []) rv[m] += iv rv[m] += jv return True def unique(l): """flatten list-of-lists excluding duplicates""" seen = set() for i in sum(l, []): if i not in seen: seen.add(i) yield i def condense(inp): rv.clear() inp = map(List, inp) for i in range(len(inp)): inp[i].order = i rv.setdefault(frozenset(inp[i]), []) rv[frozenset(inp[i])].append(inp[i]) while condense_step(): pass for v in rv.values(): v.sort(key=lambda x: x.order) return [list(unique(i)) for i in rv.values()]

This solution uses only an Ordered Dictionary.
**deepcopy()** is necessary if one wants the original copy to remain unchanged.

from collections import OrderedDict from copy import deepcopy def treat(passed_list): L = deepcopy(passed_list) dic = OrderedDict() for subl in L: for x in subl: if x not in dic: dic[x] = subl print 'dic at start' print '\n'.join('%-3s : %s' % (a,dic[a]) for a in dic) + '\n' for sublist in L: short = [] short.extend(el for el in sublist if el not in short) seen = [] for k,val in dic.iteritems(): if val is sublist: break if k in short: if val not in seen: seen.append(val) sumseen = [] for elseen in seen: for y in elseen: sumseen.append(y) dic[y] = sumseen if seen: for el in sublist: if el not in sumseen: sumseen.append(el) dic[el] = sumseen sublist[:] = short cumul = [] cumul.extend(lu for lu in dic.itervalues() if lu not in cumul) return cumul plus = [[1,2,3,2,1],[10,5,5,5,10], [8,5,3,3,5],[45,50,12,45,40,12]] lst = [[1,2,3], [10,5], [3,8,5]] for one_list in (plus,lst): print 'one_list before == %r\n' % one_list print 'treat(one_list) == %r\n' % treat(one_list) print 'one_list after == %r\n' % one_list print '===================================='

result

one_list before == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]] dic at start 1 : [1, 2, 3, 2, 1] 2 : [1, 2, 3, 2, 1] 3 : [1, 2, 3, 2, 1] 10 : [10, 5, 5, 5, 10] 5 : [10, 5, 5, 5, 10] 8 : [8, 5, 3, 3, 5] 45 : [45, 50, 12, 45, 40, 12] 50 : [45, 50, 12, 45, 40, 12] 12 : [45, 50, 12, 45, 40, 12] 40 : [45, 50, 12, 45, 40, 12] treat(one_list) == [[1, 2, 3, 10, 5, 8], [45, 50, 12, 40]] one_list after == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]] ==================================== one_list before == [[1, 2, 3], [10, 5], [3, 8, 5]] dic at start 1 : [1, 2, 3] 2 : [1, 2, 3] 3 : [1, 2, 3] 10 : [10, 5] 5 : [10, 5] 8 : [3, 8, 5] treat(one_list) == [[1, 2, 3, 10, 5, 8]] one_list after == [[1, 2, 3], [10, 5], [3, 8, 5]] ====================================

This solution has an inconvenience: it is 2 to 3 times slower than the J.F. Sebastian's solution.