How to split a list of a list in a specific way in Python

Question

Given a list of integers, the task is to write a function that will output another list of integers. It is difficult to say the nature of the desired conclusion in words; I am writing a few examples:

# list with one element will be returned >>> func([[1, 2, 3, 4]]) [[1, 2, 3, 4]] >>> func([[1], [1, 2]]) [[1], [2]] >>> func([[1, 2], [1]]) [[1], [2]] >>> func([[1], [1, 2, 3]]) [[1], [2, 3]] >>> func([[1], [1, 2, 3], [1, 4]]) [[1], [2, 3], [4]] >>> func([[1, 2], [2, 3]]) [[1], [2], [3]] >>> func([[1], [2], [1, 2, 3]]) [[1], [2], [3]] >>> func([[1, 2], [1, 2, 3]]) [[1, 2], [3]] >>> func([[1], [1, 2], [1, 2, 3]]) [[1], [2], [3]] 

(UPDATE) You can use the following prerequisites:

• Each internal list contains integers that are already sorted and have no duplicate entries.

• The external list has no duplicate entries.

(UPDATE) As you asked, here's what I think is stuck:

This is a problem of some optimization on the Directed Graph, with numbers as nodes and internal lists as starting points of edges (an external list is a set of starting points of all edges). Now you may ask: "How are several starting points for one edge, what is shown in some test cases?"

This is what I am trying to do: for func ([1, 2]) node 1 and node 2 can be combined with one node. The output [1, 2] shows that these two can be combined.

Now let's look at func ([[1], [1, 2]]) . The second internal list tries to merge node 1 and 2 together, but the first internal list says that node 1 cannot be merged with anything. Thus, the output [[1], [2]] indicating that node 1 and node 2 should be separated.

For func ([[1], [2, 3], [1, 2, 3]]) , node 1 needs to be separated, but node 2 and 3 can be combined; therefore the output will be [[1], [2, 3]]

In the case of func ([[1, 2], [2, 3]]) neither node 1 and 2, nor 2 and 3 can be combined, since node 1 and 3 can be combined, so the expected result is [[1], [2], [3]] .

There is also a list of integers that contains the end points of the vertices; each integer corresponds to each internal list. When elements of the internal list are combined with one, only 1 edge remains. When they are separated, there are plain lists, and the elements from each of them are taken as starting points; the list of endpoints is updated accordingly.

I think this will help you realize my needs.

Answer 1

It depends on the list of lists sorted by increasing length (and the outputs need sorting), but it works with all the inputs provided since publication.

 def removeFromList(elementsToRemove): def closure(list): for element in elementsToRemove: if list[0] != element: return else: list.pop(0) return closure def func(listOfLists): result = [] for i, thisList in enumerate(listOfLists): result.append(thisList) map(removeFromList(thisList), listOfLists[i+1:]) return result 

You can remove the closure by using more for loops, but it looked too ugly and too deeply nested.

Edit: Based on updates, this is a naive solution to the problem itself:

 from itertools import combinations def isSubsetOrDisjointTo(listA, listB): return all(item in listB for item in listA) or all(item not in listB for item in listA) def func(nodesToJoin): #flatten list, extracting duplicates allNodes = sorted(set(itertools.chain(*nodesToJoin))) result = [] seen = set() for length in xrange(max(map(len, nodesToJoin)), 0, -1): #start with longest possible, work to shortest for sublist in combinations(allNodes, length): if any(item in seen for item in sublist): #skip possible sublists with options we've already seen in the result continue if all(isSubsetOrDisjointTo(sublist, node) for node in nodesToJoin): result.append(sublist) seen.update(sublist) return result 

There may be several ways to optimize or improve.

Answer 2

 def func(L): r = [L[0]] for i in range(1, len(L)): r.append(list(set(L[i]) - set(L[i-1]))) return r 

Answer 3

 def f (L): return [[l for l in L[i] if l not in sum(L[:i], [])] for i in range(len(L))] 

Edit: OP continues to change what the test results are for, so that I don’t know, this gives the correct answers to all the tests that were there when I wrote it.