Karşılaştırma işlevine göre öğeleri nasıl verimli bir şekilde gruplandırabilirsiniz?

Question

Öğelerin bir listesi ve bir boolean döndüren bir f (item1, item2) karşılaştırma işlevi var.

Aynı gruptaki tüm öğelerin f (itemi, itemj) === true koşulunu karşılayabilmesi için bu öğelerden gruplar oluşturmak istiyorum.

Bir öğe birkaç gruba dahil edilebilir. Bir grup için minimum boyut yoktur.

Bunun için javascript (veya başka bir dilde) etkin bir algoritma yazmaya çalışıyorum. Ben oldukça kolay olacağını düşündüm ama bir gün sonra hala üzerinde yaşıyorum ...

Herhangi bir işaretçi çok takdir edilecektir!

, işte

Answer 1

Tamam (Öğelerimin dizinin maksimum boyutu yardım ederse, 1000) Sonunda öyle yapmıştım. Bu durumun tamamen doğru olduğundan emin değilim ama şimdiye kadar iyi sonuçlar veriyor.

İki aşama vardır; ilk önce, koşulla eşleşen gruplar oluşturma hakkında. İkincisi, kopyaları veya içerilen grupları kaldırmaktır. Bunun yerine ürünleri kullanmak öğelerin

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); 
     } 
    }); 
} 

, benim gerçek bir kullanım durumu:

İşte ilk bölümü için kod, ikinci bölüm oldukça önemsiz eğer bu. f (item1, item2) & & f (madde2, öğe1) için iki koşullu sınamalar. Hızlanmayı hızlandırmak ve hesaplamaktan kaçınmak için, tüm durum sonuçlarının bir matrisini oluşturdum ve bu matrisi biCondition işlevinde kullanıyorum.