最近、以下に概説するセットの問題に対する単純な再帰アルゴリズムを開発する必要がありましたが、問題の正式な説明/名前が何であるか、および問題をより効率的に解決できるアルゴリズムがあるかどうかを知りたいです (私はそこにあると思いますは）。
交差と非結合を見つけるための個別のアルゴリズムがあることは知っていますが、この問題全体をカバーするアルゴリズムは認識していません。
問題：
不定数のセットを取得し、すべてのセットの交差および非交差ごとに 1 つのセットを返す。
たとえば、入力 A、B、C、D として 4 つのセットがあるとします。
{1,14,2,10,13,12,8,9}
B{2,3,4,15,11,13,9}
C{13,10,4,15,5,6,12,11}
D {7,8,9,13,11,6,12}
結果は次の 13 セットになります。
{1,14},{2},{3},{4,15},{5},{6},{7},{8},{9},{10},{11},{12 }、{13}
私が開発したアルゴリズムは、交差が見つからなくなるまで、すべてのセット順列を再帰的に比較するという単純なものでした (XSLT 2.0 でこれを比較的簡単に実装できるようにしたかったのです)。
いくつかのコンテキストでは、ツリーの各ポイントで、ツリーの複数のバージョンが元のツリーをどのように変更するかを説明するために、この操作を実行する必要がありました。「ツリー」は実際には XML ドキュメントです。
[更新] 3 つのセットに対する受け入れられた回答実行の最初のアルゴリズムを表示: {1,2,3}、{2,3,4}、{2,3,5}
3 つのセットで実行される元の nieve アルゴリズムと比較すると、次のようになります。
