2016-04-11 14 views
0

私はアイテムのリストと比較関数f(item1、item2)を持っています。これはブール値を返します。比較機能に基づいてアイテムを効率的にグループ化する方法はありますか?

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

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

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

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

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

+0

私はいろいろ試しましたが、実装に失敗しました。たとえば、すべての組み合わせを使用して0と1の行列を作成し、列と行を移動して1の正方行列を探しますが、実装するのは簡単ではありません。もう1つは各列(itemiにすべて一致)で実行し、ツリー内にファッションのようにグループを生成することでした。私の主な問題は、問題に取り組むための明確な方法が実際にはなく、よく知られているタイプの問題/アルゴリズムに対応することを望んでいたことです。 – Thomas

+0

まず、 'f(itemi、itemj)=== f(itemj、itemi)'ですか?そして、はいの場合は、項目が複数のグループに含まれるという例がありますか? – Thomas

+0

いいえ、必ずしも – Thomas

答えて

0

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関数で使用しました。

関連する問題