如何根據比較功能有效地分組項目？

我有一個項目列表和比較函數f（item1，item2），它返回一個布爾值。如何根據比較功能有效地分組項目？

我想從這些項目中生成組，以便同一組中的所有項滿足條件f（itemi，itemj）=== true。

一個項目可以包含在幾個組中。一個組沒有最小尺寸。

我想寫一個JavaScript（或其他語言）的高效算法。我認爲這將是非常容易的，但我仍然在一天後左右...

任何指針將不勝感激！

（我的項目陣列的最大尺寸爲1000，如果它可以幫助）

2016-04-11 Thomas

我已經嘗試了各種各樣的東西，但是在實現它們時卻失敗了。例如，我使用所有組合創建了一個0和1的矩陣，並通過移動列和線來尋找1的方形子矩陣，但不容易實現！另一個是在每一列上運行（全部匹配itemi），然後在樹中像時尚一樣生成組。我想我的主要問題是我沒有一個明確的方法來解決這個問題，並且希望它能夠符合一個衆所周知的問題/算法。 – Thomas

首先是'f（itemi，itemj）=== f（itemj，itemi）'？如果是的話，請求提供了一個例子，那麼一個項目將被包含在多個組中？ – Thomas

不，不一定 – Thomas

好了，這裏就是我最終做到了。我仍然不確定這是完全正確的，但它迄今爲止取得了良好的結果。

有兩個階段，第一個階段是關於創建符合條件的組。第二個是關於刪除任何重複或包含的組。

這裏的，如果很平凡的第一部分的代碼，第二部分：

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）的bimindition測試。爲了加速和避免微積分的重複，我創建了一個所有條件結果的矩陣，並在biCondition函數中使用這個矩陣。

來源

2016-04-12 09:30:30 Thomas

如何根據比較功能有效地分組項目？

回答

相關問題