我有一堆类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

最佳答案

好的,您可以使用一种方法来测量对象之间的相似性。这意味着它们形成一个Metric Space

问题是,您的空间还是像普通的三维空间一样的Euclidean space还是整数或类似的东西?如果是的话,那么您可以在任意多个维度中使用binary space partition

(问题是,基本上是:您的对象与n维实数向量之间是否存在同态?如果是,则可以使用技术来测量n维空间中点的紧密度。)

现在,如果它不是欧几里德空间,那么您将面临更大的问题。程序员可能最熟悉的非欧几里德空格的示例是字符串之间的Levenshtein Distance

如果您的问题类似于查看字符串与已存在的字符串列表的相似性,那么我不知道没有O(n2)时间就能做到的算法。也许那里有一些。



但是另一个重要的问题是:您有多少时间?有多少个物体?如果您有时间或数据集足够小以至于可以使用O(n2)算法,则只需要遍历对象列表以查看其是否低于某个阈值即可。如果是这样,请拒绝它。

只需重载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必须是您可以对其进行比较的某个类的子类。如果您具有欧几里德度量标准,则可以使用空间分区,而不要遍历其他所有项目。

09-10 07:18
查看更多