比較機能に基づいてアイテムを効率的にグループ化する方法はありますか？

Question

私はアイテムのリストと比較関数f（item1、item2）を持っています。これはブール値を返します。

同じグループのすべてのアイテムが条件f（itemi、itemj）=== trueを満たすように、これらのアイテムからグループを生成したいとします。

アイテムはいくつかのグループに含めることができます。グループの最小サイズはありません。

私はそれのためのJavaScript（または他の言語）で効率的なアルゴリズムを記述しようとしています。私はそれがかなり簡単だと思ったが、私は1日後にまだそれになっている...

すべてのポインタが高く評価される！

（それは場合に役立ちます私の項目の配列の最大サイズは、1000年である）

Answer 1

OKなので、ここで私は最後にそれをやった方法です。私はまだこれが完全に正しいと確信していますが、これまでのところ良い結果が得られています。

2つのフェーズがあります。最初は、条件に一致するグループを作成することです。 2つ目は、重複または含まれているグループを削除することです。代わりに、私は製品を使用するアイテムの

for(index = 0; index < products.length; index++) { 
    existingGroups = []; 
    seedProduct = products[index]; 
    for(secondIndex = index + 1; secondIndex < products.length; secondIndex++) { 
     candidateProduct = products[secondIndex]; 
     if(biCondition(seedProduct, candidateProduct)) { 
      groupFound = false; 
      existingGroups.forEach(function(existingGroup) { 
       // check if product belongs to this group 
       isPartOfGroup = true; 
       existingGroup.forEach(function(product) { 
        isPartOfGroup = isPartOfGroup && biCondition(product, candidateProduct); 
       }); 
       if(isPartOfGroup) { 
        existingGroup.push(candidateProduct); 
        groupFound = true; 
       } 
      }); 
      if(!groupFound) { 
       existingGroups.push([candidateProduct]); 
      } 
     } 
    } 
    // add the product to the groups 
    existingGroups.forEach(function(group) { 
     group.push(seedProduct); 
     if(group.length > minSize) { 
      groups.push(group); 
     } 
    }); 
} 

、私の本当のユースケースである：

は、ここで最初の部分のコードを、第二部は非常に些細な場合です。 f（item1、item2）& & f（item2、item1）のバイコンディションテスト。微積分の高速化と重複を避けるために、私はすべての条件結果の行列を作成し、この行列をbiCondition関数で使用しました。