したがって、"picture" と "turepic" で同じ結果が得られるハッシュコード計算が必要ですが、(できれば) "eruptic" などのハッシュコードとは異なります。したがって、単語に含まれる文字のハッシュコードを単純に合計するだけでは十分ではありません。位置情報も必要ですが、単語の実際の順列とは無関係である必要があります。「等価クラス」を定義し、クラスの各メンバーに対して常に同じハッシュコードを計算する必要があります。
これを実現する最も簡単な方法は、同値クラスの特定のメンバーを選択し、すべての同値語に対して常にそのバリエーションのハッシュコードを使用することです。たとえば、最初のバリアントをアルファベット順に選択します（簡潔にまとめてくれた@Michaelに感謝します）。「picture」などの場合は、「cturepi」になります。「picture」と「turepic」の両方 (および他のすべての同等のバリエーション) は、「cturepi」のハッシュ コードを返す必要があります。そのハッシュ コードは、標準の LinkedList メソッドまたはその他の推奨される方法で計算できます。
この計算は非常にコストがかかると言う人もいるかもしれません。確かにそうですが、最初の計算だけがコストがかかるように、結果をキャッシュすることはできます。そして、最初のアルファベット順のバリアントの選択は、一般的なケースではかなり最適化できると思います(特定の等価クラスですべての順列を生成し、それらを並べ替えて最初のものを選択するという簡単な解決策と比較して)。
たとえば、多くの単語では、アルファベット順の最初の文字が一意です (「picture」はその 1 つです。アルファベット順の最初の文字は 'c' で、'c' は 1 つしかありません)。したがって、それを見つけて、そこからハッシュコードを計算するだけです。一意でない場合は、違いが見つかるまで (またはロールオーバーするまで)、その後の 2 番目、3 番目などの文字を比較する必要があります。
更新 2 - 例
- 「abracadabra」には 5 つの「a」が含まれています。「a」の後の 2 番目の文字は、それぞれ「b」、「c」、「d」、「b」、および「a」です。したがって、2 回目の比較では、辞書編集的に最小のバリエーションは「aabracadabr」であると結論付けることができます。
- 「abab」には 2 つの 'a' と、それぞれの後に 'b' が含まれています (その後、ロールオーバーして再び 'a' に到達すると、クエストはそこで終了します)。したがって、辞書編集的に最小の2つの同一のバリエーションがあります。しかし、それらは同一であるため、明らかに同じハッシュコードを生成します。
更新:最終的には、ハッシュコードが実際にどれだけ必要かということになります。つまり、循環リストを or のような連想コレクションに入れる予定がありますSetかMap? そうでない場合は、単純な、または簡単なハッシュ メソッドを使用できます。しかし、連想コレクションを頻繁に使用すると、単純なハッシュ実装では多くの衝突が発生するため、最適なパフォーマンスが得られません。この場合、このハッシュ方式を実装して、パフォーマンスに見合うかどうかを測定してみる価値があります。
更新 3: サンプル コード
Letterは基本的に上記と同じままです。フィールドのみを作成し、名前をprivateに変更theNextNodeしnext、必要に応じてゲッター/セッターを追加しました。
ではさらにCircularWordいくつか変更を加えtailましtheCurrentNodeたlast.next == head。コンストラクターtoStringとequalsは、ハッシュコードの計算には関係ないため、簡単にするために省略されています。
public class CircularWord {
private final Letter head;
private final int numberOfElements;
// constructor, toString(), equals() omitted
@Override
public int hashCode() {
return hashCodeStartingFrom(getStartOfSmallestRotation());
}
private Letter getStartOfSmallestRotation() {
if (head == null) {
return null;
}
Set<Letter> candidates = allLetters();
int counter = numberOfElements;
while (candidates.size() > 1 && counter > 0) {
candidates = selectSmallestSuccessors(candidates);
counter--;
}
return rollOverToStart(counter, candidates.iterator().next());
}
private Set<Letter> allLetters() {
Set<Letter> letters = new LinkedHashSet<Letter>();
Letter letter = head;
for (int i = 0; i < numberOfElements; i++) {
letters.add(letter);
letter = letter.getNext();
}
return letters;
}
private Set<Letter> selectSmallestSuccessors(Set<Letter> candidates) {
Set<Letter> smallestSuccessors = new LinkedHashSet<Letter>();
char min = Character.MAX_VALUE;
for (Letter letter : candidates) {
Letter nextLetter = letter.getNext();
if (nextLetter.getValue() < min) {
min = nextLetter.getValue();
smallestSuccessors.clear();
}
if (nextLetter.getValue() == min) {
smallestSuccessors.add(nextLetter);
}
}
return smallestSuccessors;
}
private Letter rollOverToStart(int counter, Letter lastCandidate) {
for (; counter >= 0; counter--) {
lastCandidate = lastCandidate.getNext();
}
return lastCandidate;
}
private int hashCodeStartingFrom(Letter startFrom) {
int hash = 0;
Letter letter = startFrom;
for (int i = 0; i < numberOfElements; i++) {
hash = 31 * hash + letter.getValue();
letter = letter.getNext();
}
return hash;
}
}
単語の辞書編集的に最小のローテーションを見つけるために実装されたアルゴリズムgetStartOfSmallestRotationは、基本的には上記で説明したものです。各ローテーションの辞書編集的に最小の 1 番目、2 番目、3 番目などの文字を比較して選択し、残りの候補が 1 つだけになるまで大きい文字を削除します。 、または単語をロールオーバーします。リストは循環しているため、カウンターを使用して無限ループを回避します。
最終的に、候補が 1 つ残っている場合、それは単語の途中にある可能性があり、最小の単語ローテーションの開始点を取得する必要があります。ただし、これは片方向リストであるため、後ろに下がるのは面倒です。幸いなことに、カウンターは私をうまく助けてくれます。これまでに比較した文字数が記録されていますが、循環リストでは、ロールオーバーする前に前方に移動できる文字数に相当します。したがって、探している最小限の単語のローテーションの先頭に戻るために何文字進むべきかがわかります。
これが誰かの役に立てば幸いです-少なくとも書くのは楽しかったです:-)