Using sublists to create new lists where numbers don't repeat

Question

Given a list:

g = [[0, 7], 
     [1, 2, 10, 19],
     [3, 4, 5, 6, 15, 21, 24, 27],
     [0, 7, 8, 9, 12, 17],
     [1, 10, 11, 20],
     [8, 12, 13, 18],
     [14, 25],
     [3, 15, 16, 22],
     [9, 13, 17, 18]]

I want to check the numbers in the sublist so that for any number that exists in more than one sublist, both sublists can combine to form a new list, e.g. [8, 12, 13, 18] and [9, 13 ,17, 18] can combine to give [8, 9, 12, 13, 17, 18]. Note: the number doesn't repeat and I want to make the biggest possible list.

I have written the following code, but it is not perfect and repeat has not be eliminated, can anyone help?

for i in g:
    for j in g:
        for k in i:
            for l in j:
                if k  == l:
                    m=list(set(i + j))
                    if m not in n:
                        n.append(m)

My expected output is:

[[0, 7, 8, 9, 12, 13, 17, 18],
 [1, 2, 10, 11, 19, 20],
 [3, 4, 5, 6, 15, 16, 21, 22, 24, 27],
 [25, 14]]

What is the expected output for the input you have given here? — Kevin, Jan 06 '15 at 16:28
Sounds like a job for [`sets`](https://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset) — David Reeve, Jan 06 '15 at 16:30
when you iterate the second time you start comparing lists to themselves, meaning every list will be appended to n as they all compare accurately to themselves — NDevox, Jan 06 '15 at 16:31
@Na Lai add your expected output as the question can be interpreted a few different ways, do you mean if 13 is used and it is in a third list you ignore that list? — Padraic Cunningham, Jan 06 '15 at 16:33
sorry for be confusing. My expected output is [[0, 7, 8, 9, 12, 13, 17, 18], [1, 2, 10, 11, 19, 20], [3, 4, 5, 6, 15, 16, 21, 22, 24, 27], [25, 14]] — James Harroid, Jan 06 '15 at 16:44

jonrsharpe · Accepted Answer · 2015-01-06T16:58:59.963

Starting from your initial list of lists:

>>> g = [[0, 7], 
         [1, 2, 10, 19],
         [3, 4, 5, 6, 15, 21, 24, 27],
         [0, 7, 8, 9, 12, 17],
         [1, 10, 11, 20],
         [8, 12, 13, 18],
         [14, 25],
         [3, 15, 16, 22],
         [9, 13, 17, 18]]

As you work through, I think what you want is to combine all matching sublists in the rest of the list into the current sublist, then remove them from the original list:

>>> for start_index, start in enumerate(g):
    while True:
        for end_index, end in enumerate(g[start_index+1:],
                        start_index+1):
            if any(x == y for x in start for y in end):
                g[start_index].extend(end)
                del g[end_index]
                break
        else:
            break


>>> g
[[0, 7, 0, 7, 8, 9, 12, 17, 8, 12, 13, 18, 9, 13, 17, 18], 
 [1, 2, 10, 19, 1, 10, 11, 20], 
 [3, 4, 5, 6, 15, 21, 24, 27, 3, 15, 16, 22], 
 [14, 25]]

Then all you have to do is get rid of duplicates:

>>> [sorted(set(l)) for l in g]
[[0, 7, 8, 9, 12, 13, 17, 18], 
 [1, 2, 10, 11, 19, 20], 
 [3, 4, 5, 6, 15, 16, 21, 22, 24, 27], 
 [14, 25]]

This is relatively inefficient, but provides you a starting point for enhancement (for example, if start and end were already sets, start & end could replace the any).

hi thank you so much, but can you explain the start_index, start in enumerate(g):, for me please? I don't quite understand the code, especially enumerate — James Harroid, Jan 07 '15 at 19:47
Have you tried [reading the docs](https://docs.python.org/2/library/functions.html#enumerate)? If you don't understand, try putting in some `print`s to see what's happening. — jonrsharpe, Jan 07 '15 at 19:49
This code has O(n^2) complexity. If limited numbers are there and using dict is allowed, it can be done in single iteration. — jerrymouse, Jan 08 '15 at 21:50

Using sublists to create new lists where numbers don't repeat

1 Answers1

Linked

Related