2

我有一堆类的对象Puzzle。我已经覆盖了equals()and hashCode()。当需要向用户展示解决方案时，我想过滤掉所有“相似”的谜题（按照我定义的标准），所以用户只能看到每个谜题中的一个。

相似性是可传递的。

例子：

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

在这种情况下，只有 A 或 D 和 B 或 C 会呈现给用户——而不是两个类似的拼图。两个类似的谜题同样有效。重要的是它们不会同时显示给用户。

为此，我想使用一个禁止重复的 ADT。但是，我不想更改equals()andhashCode()方法来返回关于相似性的值。Equalator在这种情况下，Comparator我可以使用一些吗？还是我应该这样做的另一种方式？

我正在学习的课程是一个维护字母网格的拼图。（如拼字游戏。）如果拼图包含相同的单词，但方向不同，则认为它是相似的。所以下面要解惑：

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

将类似于：

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

5 回答 5

2

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() {
        // ...
    }
}

然后你把所有的谜题包起来，把它们放在地图上，然后再把它们拿出来……

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();
}
于 2010-01-01T05:20:25.227 回答
2

好的，您有一种测量对象之间相似性的方法。这意味着它们形成了一个Metric Space。

问题是，你的空间也是像普通三维空间一样的欧几里得空间，还是整数或类似的东西？如果是，那么您可以在任何维度上 使用二进制空间分区。

（问题基本上是：您的对象和 n 维实数向量之间是否存在同态？如果是，那么您可以使用技术来测量 n 维空间中点的接近度。）

现在，如果它不是欧几里得空间，那么你就有一个更大的问题。程序员可能最熟悉的非欧几里得空间的一个例子是字符串之间的Levenshtein 距离。

如果您的问题类似于查看字符串与现有字符串列表的相似程度，那么我不知道有任何算法可以在没有 O(n 2 ) 时间的情况下做到这一点。也许有一些在那里。

但另一个重要问题是：你有多少时间？有多少对象？如果您有时间或者如果您的数据集足够小以至于 O(n 2 ) 算法是实用的，那么您只需遍历对象列表以查看它是否低于某个阈值。如果是这样，拒绝它。

只需重载AbstractCollection并替换 Add 函数。使用 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 需要是某个类的子类，您可以对其进行比较。如果您有欧几里得度量，那么您可以使用空间分区，而不是遍历所有其他项目。

于 2010-01-01T05:21:13.593 回答
2
  1. 使用 Comparator 创建 TreeSet
  2. 将所有元素添加到集合中
  3. 所有重复项都被删除
于 2010-04-30T20:56:33.857 回答
0

通常，“相似性”不是传递关系。所以第一步是从等价而不是相似的角度来考虑这一点。等价是自反的、对称的和传递的。

这里的简单方法是定义一个拼图包装器，其 equals() 和 hashCode() 方法是根据所讨论的等价关系实现的。

完成后，将包装的对象放入 java.util.Set 并过滤掉重复项。

于 2010-04-30T21:14:46.920 回答
0

恕我直言，Gili（带有自定义比较器的 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;
}
于 2014-07-30T17:14:53.177 回答