ホームページ > バックエンド開発 > Python チュートリアル > グラフ理論を使用して重複する要素を持つリストをマージする方法?

グラフ理論を使用して重複する要素を持つリストをマージする方法?

Susan Sarandon
リリース: 2024-10-21 17:14:02
オリジナル
199 人が閲覧しました

How to Merge Lists with Overlapping Elements Using Graph Theory?

リストと共有要素の結合: グラフ理論的アプローチ

リストのコレクションがあり、その一部には重複する要素が含まれているとすると、目的はそれらを、元のリスト全体の一意の要素の完全なセットで構成されるリストのセットに統合することです。たとえば、次のリストの入力リストを考えてみましょう:

L = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
ログイン後にコピー

タスクは、共通の要素を共有するリストを、結合できるリストがなくなるまで結合することです。望ましい出力は次のとおりです。

L = [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'o', 'p'], ['k']]
ログイン後にコピー

ブール演算と while ループを使用することもできますが、リストをグラフとして表示することで、より効率的なアプローチを見つけることができます。グラフ表現では、各リストはエッジで接続されたノードのセットに対応します。したがって、この問題は、このグラフ内の接続コンポーネントを見つけることになります。

1 つの解決策には、次に示すように、グラフ分析用の堅牢なライブラリである NetworkX を利用することが含まれます。

<code class="python">import networkx 
from networkx.algorithms.components.connected import connected_components

def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print(connected_components(G))
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]</code>
ログイン後にコピー

グラフ理論に基づいて、NetworkX はタスクを効果的に処理し、正確さと効率性を確保します。

以上がグラフ理論を使用して重複する要素を持つリストをマージする方法?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:php
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート