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