オブジェクト A、B、C、D があるとします。たとえば、A は B と C を参照し、C は A を参照する可能性があります。セグメントを作成したいが、2 回作成したくないので、セグメント AC とセグメント CA は必要ありません。それらの1。だから私は作成されたセグメントのリストを保持したいと思っています.
これを行うことができるデータ構造はありますか?
ありがとう
if(list.contains(a,b)
{
//dont add
}
オブジェクト A、B、C、D があるとします。たとえば、A は B と C を参照し、C は A を参照する可能性があります。セグメントを作成したいが、2 回作成したくないので、セグメント AC とセグメント CA は必要ありません。それらの1。だから私は作成されたセグメントのリストを保持したいと思っています.
これを行うことができるデータ構造はありますか?
ありがとう
if(list.contains(a,b)
{
//dont add
}
あなたは次のようなものを紹介するかもしれません
class PairKey<T extends Comparable<T>> {
final T fst, snd;
public PairKey(T a, T b) {
if (a.compareTo(b) <=0 ) {
fst = a;
snd = b;
} else {
fst = b;
snd = a;
}
}
@Override
public int hashCode() {
return a.hashCode() & 37 & b.hashCode();
}
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (!(other instanceOf PairKey)) return false;
PairKey<T> obj = (PairKey<T>) other;
return (obj.fst.equals(fst) && obj.snd.equals(snd));
}
}
次に、エッジを HashSet < PairKey < ? extends Comparable> > 次に、指定されたペアが既に存在するかどうかを確認します。
頂点を比較可能にする必要があるため、PairKey(A,B) を PairKey(B,A) と同等に扱うことができます。
その後、HashSet が残りの処理を行います。たとえば、クエリを実行できます。
pairs.contains(new PairKey(A,B));
ペアが PairKey(A,B) または PairKey(B,A) のいずれかを含む場合、true が返されます。
hashCode の実装は若干異なる可能性があります。IDE がより洗練されたものを生成する可能性があります。
それが役立つことを願っています。
Pair
次のような オブジェクトを使用します。
class Pair
{
Node start;
Node end;
public Pair(Node start, Node end)
{
this.start=start;
this.end=end;
}
public Pair reverse()
{
return new Pair(end,start);
}
}
これで、次のようなことができます。
if(pairs.contains(currentPair) || pairs.contains(currentPair.reverse())
{
continue;
} else{
pairs.add(currentPair);
}
コメントで指摘されているように、equals と hashcode を実装する必要があります。ただし、equals でチェックを行ってセグメントの反転と一致させることは、純粋な OO では悪い習慣です。コメント内で説明されているように equals を実装すると、ペアはアプリケーションにのみバインドされ、その移植性が失われます。
あなたの問題はグラフ理論に関連しています。
あなたが試すことができるのは、その内部リストを削除し、すべてのオブジェクトが共有するIncidence Martrixを作成することです。
最終的な解決策は、タスクの目標と利用可能な構造に大きく依存します。あなたが提供した説明であなたの問題に最適な解決策を選択するのは難しいです.
オブジェクトのセットのセットを使用できます。
Set<Set<MyObjectType>> segments = new HashSet<Set<MyObjectType>>();
次に、 のペアを表す 2 要素セットを追加できますMyObject
。セットは順序付けされていないためsegments
、A と B のセットが含まれている場合、B と A を含むセットを追加しようとすると、既に に存在するものとして扱われsegments
ます。
Set<MyObjectType> segment = new HashSet<MyObjectType>();
segment.add(A); // A and B are instances of MyObjectType
segment.add(B);
segments.add(segment);
segment = new HashSet<MyObjectType>();
segment.add(B);
segment.add(A);
segments.add(segment);
System.out.println("Number of segments: " + segments.size()); // prints 1
java.util.Set
/を使用java.util.HashSet
して、見つけた参照を追加し続けます。
Set set1 = new HashSet();
set1.add(A), set1.Add(C), set1.Add(C)
次のように、この調査結果を外部セットに追加できます。finalSet.add(set1)
Set<Set> finalSet = new HashSet<Set>();
finalSet.add(set1);
これにより、重複が自動的に除外され、最終的にはA & C
1 つだけが残ります。