-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. 外側のリストには重複するエントリはありません。

（更新）あなたが尋ねたように、ここに私が行き詰まっていると思うものがあります：

これは、ノードとしての数値とエッジの開始点としての内部リスト (外部リストはすべてのエッジの開始点のセット) を持つ、有向グラフの一部の最適化の問題です。ここで、「いくつかのテスト ケースで示されているように、1 つのエッジに複数の開始点があるのはどうしてですか?」と疑問に思うかもしれません。

これが私がやろうとしていることです:func ([1, 2])ノード 1 とノード 2 は単一のノードにマージできます。出力[1, 2]は、これら 2 つをマージできることを示しています。

を見てくださいfunc ([[1], [1, 2]])。2 番目の内側のリストはノード 1 と 2 を一緒にマージしようとしますが、1 番目の内側のリストはノード 1 を何にもマージできないことを示しています。したがって、出力は[[1], [2]]であり、ノード 1 とノード 2 を分離したままにすることを示します。

の場合func ([[1], [2, 3], [1, 2, 3]])、ノード 1 は分離されますが、ノード 2 と 3 はマージできます。したがって、出力は次のようになります[[1], [2, 3]]

の場合、func ([[1, 2], [2, 3]])ノード 1 と 3 はマージできるため、ノード 1 と 2 も 2 と 3 もマージできないため、期待される結果は[[1], [2], [3]]です。

頂点の端点で構成される整数のリストもあり、各整数は各内部リストに対応します。内部リストの要素が 1 つにマージされると、エッジは 1 つだけ残ります。それらが分離されると、シングルトンリストがあり、それぞれの要素が開始点として取られます。それに応じてエンドポイントのリストが更新されます。

私のニーズを理解するのに役立つと思います。

4

3 に答える 3

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 に答える