Java：Equalator？ （刪除對象集合中的重複項）

Question

我有一堆類Puzzle的對象。我已覆蓋equals()和hashCode()。當需要向用戶展示解決方案時，我想篩選出所有「相似」的謎題（按我定義的標準），因此用戶只能看到其中的一個。

相似性是可傳遞的。

實施例：

Result of computations: 
A (similar to A) 
B (similar to C) 
C 
D 

在這種情況下，僅A或d和B或C將被呈現給用戶的 - 但不是兩個類似的難題。兩個類似的謎題同樣有效。僅向用戶顯示它們纔是重要的。

爲了達到這個目的，我想使用禁止重複的ADT。但是，我不想更改equals()和hashCode()方法來返回有關相似性的值。是否有一些Equalator，如Comparator，我可以在這種情況下使用？還是有另一種方式我應該這樣做？

我正在處理的課程是一個謎題，它保持着一個字母網格。 （如拼字遊戲。）如果拼圖包含相同的單詞，但方向不同，它被認爲是相似的。所以下面的困擾：

        (2, 2): A   
            (2, 1): C   
            (2, 0): T 

將類似於：

    (1, 2): A   
        (1, 1): C   
        (1, 0): T  

Answer 1

我會用它覆蓋equals和hashCode相應的包裝類。

private static class Wrapper { 
    public static final Puzzle puzzle; 
    public Wrapper(Puzzle puzzle) { 
     this.puzzle = puzzle; 
    } 
    @Override 
    public boolean equals(Object object) { 
     // ... 
    } 
    @Override 
    public int hashCode() { 
     // ... 
    } 
} 

然後你把所有的謎題都包裝好，放在地圖上，再把它們拿出來...... hellip;

public Collection<Collection<Puzzle>> method(Collection<Puzzles> puzzles) { 
    Map<Wrapper,<Collection<Puzzle>> map = new HashMap<Wrapper,<Collection<Puzzle>>(); 
    for (Puzzle each: puzzles) { 
     Wrapper wrapper = new Wrapper(each); 
     Collection<Puzzle> coll = map.get(wrapper); 
     if (coll == null) map.put(wrapper, coll = new ArrayList<Puzzle>()); 
     coll.add(puzzle); 
    } 
    return map.values(); 
} 

Answer 2

好的，你有測量對象之間相似度的方法。這意味着他們形成了一個Metric Space。

問題是，你的空間也像一般的三維空間Euclidean space，或整數或類似的東西？如果是這樣，那麼你可以使用一個binary space partition不管你有多少維度。

（現在的問題是，基本上是：有沒有你的對象和n維實數向量之間的同態。如果是這樣，那麼你可以用技術在n維空間測量點的接近？）

現在，如果它是而不是一個歐幾里得空間，那麼你遇到了一個更大的問題。程序員可能最熟悉的非歐幾里得空間的例子是字符串之間的Levenshtein Distance。

如果你的問題是相似看到一個字符串的相似程度已經存在的字符串列表，然後我不知道的，會做，沒有爲O（n ）任何時間算法。也許有一些在那裏。

---

但另一個重要的問題是：有多少時間你有嗎？多少個物體？如果您有時間，或者您的數據集足夠小以至於O算法是實用的，那麼您只需遍歷對象列表以查看它是否低於某個閾值。如果是這樣，拒絕它。

只是過載AbstractCollection並替換添加功能。使用ArrayList或其他。您的代碼看起來有點像這樣

class SimilarityRejector<T> extends AbstractCollection<T>{ 
    ArrayList<T> base; 
    double threshold; 

    public SimilarityRejector(double threshold){ 
     base = new ArrayList<T>(); 
     this.threshold = threshold; 
    } 

    public void add(T t){ 
     boolean failed = false; 
     for(T compare : base){ 
      if(similarityComparison(t,compare) < threshold) faled = true; 
     } 
     if(!failed) base.add(t); 
    } 

    public Iterator<T> iterator() { 
     return base.iterator(); 
    } 

    public int size() { 
     return base.size(); 
    } 
} 

等。很明顯，T將需要一些類，你可以對比較的子類。如果你有一個歐幾里德度量標準，那麼你可以使用空間分區，而不是每個其他項目。

Answer 3

1. 使用比較
2. 將所有元素融入到一套
3. 所有副本都剝離出來

Answer 4

通常，「相似性」是不是過渡關係創建一個TreeSet。所以第一步就是用等價性而不是相似性來考慮這一點。等價是自反的，對稱的和傳遞的。

這裏簡單的方法是定義一個拼圖封裝器，它的equals（）和hashCode（）方法根據所討論的等價關係來實現。

一旦你有了，把包裝好的對象放到一個java.util.Set中，並過濾掉重複項。

Answer 5

恕我直言，最優雅的方式是由吉利（TreeSet與自定義比較器）描述。

但是，如果你想自己做吧，看來這最簡單和最清晰的解決方案：

/** 
* Distinct input list values (cuts duplications) 
* @param items items to process 
* @param comparator comparator to recognize equal items 
* @return new collection with unique values 
*/ 
public static <T> Collection<T> distinctItems(List<T> items, Comparator<T> comparator) { 
    List<T> result = new ArrayList<>(); 

    for (int i = 0; i < items.size(); i++) { 
     T item = items.get(i); 

     boolean exists = false; 
     for (int j = 0; j < result.size(); j++) { 
      if (comparator.compare(result.get(j), item) == 0) { 
       exists = true; 
       break; 
      } 
     } 

     if (!exists) { 
      result.add(item); 
     } 
    } 

    return result; 
}