Hintergrund:
Ich arbeite mit Permutationen der Folge der ganzen Zahlen {0, 1, 2 ..., n}. Ich habe einen lokalen Suchalgorithmus, der eine Permutation auf eine systematische Weise in eine andere Permutation transformiert. Der Zweck des Algorithmus besteht darin, eine Permutation zu erzeugen, die eine Kostenfunktion minimiert. Ich würde gerne mit einer Vielzahl von Problemen arbeiten, von n = 5 bis n = 400.
Das Problem:
Um den Suchaufwand zu reduzieren, muss ich prüfen können, ob ich vorher eine bestimmte Permutation von Ganzzahlen verarbeitet habe. Ich benutze dafür eine Hash-Tabelle und ich muss in der Lage sein, eine ID für jede Permutation zu generieren, die ich als Schlüssel in die Tabelle verwenden kann. Allerdings kann ich mir keine nette Hash-Funktion vorstellen, die eine Menge von ganzen Zahlen in einen Schlüssel abbildet, so dass Kollisionen nicht zu häufig auftreten.
Sachen, die ich versucht habe:
Ich begann damit, eine Folge von n Primzahlen zu erzeugen und die i-te Zahl in meiner Permutation mit der i-ten Primzahl zu multiplizieren und dann die Ergebnisse zu summieren. Der resultierende Schlüssel erzeugt jedoch auch für n = 5 Kollisionen.
Ich dachte auch, die Werte aller Zahlen miteinander zu verketten und den ganzzahligen Wert der resultierenden Zeichenkette als einen Schlüssel zu nehmen, aber die ID wird selbst für kleine Werte von n schnell zu groß. Im Idealfall würde ich gerne jeden Schlüssel als Integer speichern können.
Hat stackoverflow irgendwelche Vorschläge für mich?
Zobrist Hashing könnte für Sie funktionieren. Sie müssen eine NxN-Matrix von zufälligen ganzen Zahlen erstellen, wobei jede Zelle das Element repräsentiert, das sich in der aktuellen Position in der j-ten Position befindet. Für eine gegebene Permutation wählen Sie die N-Zellen-Werte und xor sie einzeln aus, um den Schlüssel der Permutation zu erhalten (beachten Sie, dass die Eindeutigkeit der Schlüssel nicht garantiert ist).
Der Punkt in diesem Algorithmus ist, dass, wenn Sie zu Elementen in Ihren Permutationen wechseln, Sie einfach den neuen Schlüssel aus der aktuellen Permutation generieren können, indem Sie einfach die alte und die Xor-in an den neuen Positionen herausfiltern.
Gemessen an Ihrer Frage, und die Kommentare, die Sie verlassen haben, ich würde sagen, dass das Problem nicht möglich ist, zu lösen.
Lass es mich erklären.
Sie sagen, dass Sie einen eindeutigen Hash aus Ihrer Kombination benötigen, also machen wir diese Regel # 1:
Ok, dann haben Sie in einem Kommentar gesagt, dass, da Sie ziemlich viele Zahlen verwenden, es aufgrund von Speicherbeschränkungen nicht möglich ist, sie als String oder sonstwie als Schlüssel für die Hashtabelle zu speichern. Lassen Sie uns das in eine andere Regel umschreiben:
Im Grunde genommen versuchen Sie, eine große Zahl zu nehmen und diese in einem viel kleineren Zahlenbereich zu speichern, und haben immer noch Eindeutigkeit.
Tut mir leid, aber Sie können das nicht tun.
Typische Hashing-Algorithmen erzeugen relativ eindeutige Hash-Werte. Wenn Sie also keine Kollisionen akzeptieren, in dem Sinne, dass eine neue Kombination als "bereits gesehen" markiert wird, obwohl dies nicht der Fall ist, sind Sie nicht mehr in der Lage Glück.
Wenn Sie ein Bit-Feld ausprobieren wollten, wo jede Kombination ein Bit hat, das 0 ist, wenn es nicht gesehen wurde, brauchen Sie immer noch viel Speicher.
Für die Permutation in n = 20, die du in einem Kommentar hinterlassen hast, hast du 20! (2,432,902,008,176,640,000) Kombinationen, die, wenn Sie versuchten, einfach jede Kombination als 1-Bit in einem Bit-Feld zu speichern, 276,589TB Speicherplatz benötigen würden.
Sie müssen Ihren Umfang dessen einschränken, was Sie versuchen zu tun.
Wie andere vorgeschlagen haben, können Sie Hashing verwenden, um eine Ganzzahl zu generieren, die mit hoher Wahrscheinlichkeit eindeutig ist. Wenn Sie jedoch möchten, dass die Ganzzahl immer eindeutig ist, sollten Sie
In diesem Fall ist die ID einer Permutation ihr Index in der lexikografischen Reihenfolge. Es gibt natürlich andere Methoden, um Permutationen zu bewerten.
Indem man ids einen Bereich von stetigen ganzen Zahlen macht, ist es möglich, das Speichern verarbeiteter Permutationen als ein Bitfeld oder ein boolesches Array zu implementieren.
Sie könnten MD5 Hash eine Komma getrennte Zeichenfolge mit Ihren Ints.
In C # würde es in etwa so aussehen (Disclaimer: Ich habe keinen Compiler auf der Maschine, die ich heute benutze):
%Vor%Edit: Was habe ich gedacht? Wie von anderen angegeben, benötigen Sie keinen Hash. Die CSV-Datei sollte als String-ID ausreichen (außer Ihr Zahlen-Array ist groß).
Konvertiere jede Zahl in String, verkette Strings (über StringBuffer) und nimm den Inhalt von StringBuffer als Schlüssel.
bezieht sich nicht direkt auf die Frage, aber als alternative Lösung können Sie Trie-Baum als Nachschlage-Struktur verwenden. Trie Bäume sind sehr gut für Strings Operationen, ihre Implementierung relativ einfach und es sollte schneller sein (max von n (k) wo k ist die Länge eines Schlüssels) als hashset für eine große Menge von langen Strings. Und Sie sind nicht in der Schlüsselgröße beschränkt (wie in einem regulären hashset in must int, nicht größer). Geben Sie in Ihrem Fall eine Zeichenfolge aus allen Zahlen ein, die durch ein Zeichen getrennt sind.
Prime-Potenzen würden funktionieren: Wenn p_i das i th prim ist und a_i das i th -Element deines Tupels ist, dann
sollte durch den Fundamentalsatz der Arithmetik eindeutig sein. Diese Zahlen werden jedoch ziemlich groß: -)
(z.B. für n = 5, (1,2,3,4,5) wird 870,037,764,750 zugeordnet, was bereits mehr als 32 Bits ist)
Ähnlich wie Bojan's Post scheint es so Der beste Weg ist eine deterministische Reihenfolge der Permutationen. Wenn Sie sie in dieser Reihenfolge bearbeiten, müssen Sie nicht nachsehen, ob Sie bereits eine bestimmte Permutation durchgeführt haben.
bekomme zwei Permutationen der gleichen Reihe von Zahlen {1, .., n}, konstruiere ein Mapping-Tupel, (id, permutation1 [id], permutation2 [id]), oder (id, f1 (id), f2 ( Ich würde)); Sie erhalten eine eindeutige Karte von {f3 (id) | für tuple (id, f1 (id), f2 (id)), von id erhalten wir f2 (id) und finden eine id aus tuple (id ', f1 (id'), f2 (id ')) wo f1 (id ') == f2 (id)}