-2

给定一个整数列表，任务是编写一个函数，该函数将输出另一个整数列表。很难用语言说出所需输出的性质，我正在写一些例子：

# 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]]

（更新）您可以使用以下先决条件：

  1. 每个内部列表都包含已排序的整数，并且没有重复条目。

  2. 外部列表没有重复条目。

（更新）正如你所问，这就是我认为我坚持的：

这是有向图的一些优化问题，其中数字作为节点，内部列表作为边的起点（外部列表是所有边的起点的集合）。现在，您可能会问，“如何有多个起点指向一条边，这在某些测试用例中显示？”

这就是我想要做func ([1, 2])的：节点 1 和节点 2 可以合并到一个节点。输出[1, 2]显示这两个可以合并。

现在看看func ([[1], [1, 2]])。第二个内部列表尝试将节点 1 和 2 合并在一起，但第一个内部列表表示节点 1 不能合并到任何东西。因此，输出为[[1], [2]]，表示节点 1 和节点 2 将保持分离。

对于func ([[1], [2, 3], [1, 2, 3]])，节点 1 是要分离的，但节点 2 & 3 可以合并；所以输出将是[[1], [2, 3]]

在 的情况下func ([[1, 2], [2, 3]])，节点 1 & 2 和 2 & 3 都不能合并，因为节点 1 & 3 不能合并，所以预期结果是[[1], [2], [3]]。

还有一个整数列表，它由顶点的端点组成，每个整数对应于每个内部列表。当内部列表的元素合并为一个时，只剩下 1 条边。当它们分开时，有单例列表，并以每个列表中的元素为起点；端点列表会相应更新。

我认为这将帮助您实现我的需求。

4

3 回答 3

0 
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
于 2013-05-13T15:19:16.690 回答
0 
def f (L):
    return [[l for l in L[i] if l not in sum(L[:i], [])] for i in range(len(L))]

编辑：OP不断改变测试结果的含义，所以我不知道，这为我编写它时的所有测试提供了正确答案。

于 2013-05-13T15:19:33.163 回答
0

这依赖于按升序排序的列表列表（并且输出需要排序），但在发布时适用于所有提供的输入。

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

您可以使用更多的 for 循环来删除闭包，但它看起来太丑陋，而且嵌套太深。

编辑：基于更新，这是对实际问题的天真解决方案：

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

可能有许多方法可以优化或改进。

于 2013-05-13T16:03:33.660 回答