Ich suche nach einer reversiblen Funktion unsigned f(unsigned) , bei der die Anzahl der in f(i) gesetzten Bits mit i steigt oder zumindest nicht abnimmt. Offensichtlich muss f(0) dann 0 sein und f (~ 0) muss zuletzt kommen. Dazwischen gibt es mehr Flexibilität. Nach f (0) müssen die nächsten 32 * Werte 1U<<0 bis 1U<<31 sein, aber mir ist die Reihenfolge egal (sie haben alle 1 Bit gesetzt).
Ich möchte einen Algorithmus, der f(0)...f(i-1) nicht berechnen muss, um f(i) zu berechnen, und eine vollständige Tabelle ist auch nicht ausführbar.
Das ist Gray-Codes ähnlich, aber ich sehe keinen Weg, diesen Algorithmus wiederzuverwenden. Ich versuche, dies zu verwenden, um einen großen Datensatz zu kennzeichnen und die Reihenfolge, in der ich sie suche, zu priorisieren. Die Idee ist, dass ich einen Schlüssel C habe, und ich überprüfe Etiketten C ^ f(i) . Niedrige Werte von i sollten mir Labels ähnlich zu C geben, d. H., Die sich in nur wenigen Bits unterscheiden.
[*] Bonuspunkte, wenn Sie nicht davon ausgehen, dass unsigned 32 Bits hat.
[Beispiel] Eine gültige Anfangssequenz:
%Vor%Eine ungültige Anfangssequenz:
%Vor% Ok, scheint, als hätte ich eine vernünftige Antwort. Zuerst definieren wir binom(n,k) als die Anzahl der Möglichkeiten, wie wir k aus n Bits setzen können. Das ist das klassische Pascal-Dreieck:
Leicht berechnet und zwischengespeichert. Beachten Sie, dass die Summe jeder Zeile 1<<lineNumber ist.
Das nächste, was wir brauchen, ist die partial_sum dieses Dreiecks:
Diese Tabelle kann wiederum erstellt werden, indem zwei Werte aus der vorherigen Zeile summiert werden, mit der Ausnahme, dass der neue Eintrag in jeder Zeile jetzt 1<<line anstelle von 1 ist.
Lassen Sie uns diese Tabellen oben verwenden, um f(x) für eine 8-Bit-Zahl zu konstruieren (sie verallgemeinert sich trivialerweise auf eine beliebige Anzahl von Bits). f(0) muss immer noch 0 sein. Wenn wir die 8. Zeile im ersten Dreieck nachschlagen, sehen wir, dass die nächsten 8 Einträge f(1) bis f(9) sind, alle mit einem gesetzten Bit. Die nächsten 28 Einträge (7 + 6 + 5 + 4 + 3 + 2 + 1) haben alle 2 Bits gesetzt, also ist f (10) bis f (37). Die nächsten 56 Einträge, f (38) bis f (93), haben 3 Bits, und es gibt 70 Einträge mit 4 gesetzten Bits. Aus der Symmetrie können wir sehen, dass sie um f (128) zentriert sind, insbesondere sind es f (94) bis f (163). Und natürlich, die einzige Nummer mit 8 Bits sortiert zuletzt, wie f (255).
Mit diesen Tabellen können wir schnell bestimmen, wie viele Bits in f (i) gesetzt werden müssen. Mach einfach eine binäre Suche in der letzten Zeile deiner Tabelle. Aber das beantwortet nicht genau welche Bits gesetzt sind. Dafür brauchen wir die vorherigen Zeilen.
Der Grund dafür, dass jeder Wert in der Tabelle aus der vorherigen Zeile erstellt werden kann, ist einfach. binom (n, k) == binom (k, n-1) + binom (k-1, n-1). Es gibt zwei Arten von Zahlen mit k Bits: Diejenigen, die mit einem 0... beginnen und Zahlen, die mit 1... beginnen. Im ersten Fall müssen die nächsten n-1 -Bits diese k -Bits enthalten, im zweiten Fall müssen die nächsten n-1 -Bits nur k-1 -Bits enthalten. Sonderfälle sind natürlich 0 out of n und n out of n .
Dieselbe Struktur kann verwendet werden, um uns schnell zu sagen, was f(16) sein muss. Wir hatten bereits festgestellt, dass es 2 Bits enthalten muss, da es in den Bereich f(10) - f(37) fällt. Insbesondere ist es die Nummer 6 mit 2 gesetzten Bits (beginnend mit 0). Es ist nützlich, dies als Offset in einem Bereich zu definieren, da wir versuchen, die Länge dieses Bereichs von 28 auf 1 zu verkleinern.
Wir unterteilen diesen Bereich nun in 21 Werte, die mit einer Null anfangen und 7, die eine Eins beginnen. Seit 6 & lt; 21 wissen wir, dass die erste Ziffer eine Null ist. Von den verbleibenden 7 Bits muss immer noch 2 gesetzt werden, so dass wir eine Linie in dem Dreieck nach oben gehen und sehen, dass 15 Werte mit zwei Nullen beginnen und 6 mit 01 beginnen. Seit 6 & lt; 15, f (16) beginnt mit 00. Geht man weiter nach oben, 7 & lt; = 10, so beginnt es mit 000 . Aber 6 == 6, also beginnt es nicht mit 0000 , sondern mit 0001 . An diesem Punkt ändern wir den Anfang des Bereichs, so dass der neue Offset 0 (6-6)
Wir wissen, dass wir uns nur auf die Zahlen konzentrieren können, die mit 0001 beginnen und ein zusätzliches Bit haben, das f(16)...f(19) ist. Es sollte offensichtlich sein, dass der Bereich f(16)=00010001, f(17)=00010010, f(18)=00010100, f(19)=00011000 ist.
Also, um jedes Bit zu berechnen, bewegen wir uns eine Zeile im Dreieck nach oben, vergleichen unseren "Rest", fügen eine Null oder eine basierend auf dem Vergleich hinzu, gehen Sie möglicherweise eine Spalte nach links. Das heißt, die Berechnungskomplexität von f(x) ist O(bits) oder O(log N) und der erforderliche Speicher ist O(bits*bits) .
Für jede gegebene Zahl k wissen wir, dass es binom(n, k) n -bit Ganzzahlen gibt, die genau k Bits von Wert eins haben. Wir können nun eine Nachschlagetabelle von n + 1 ganzen Zahlen erzeugen, die für jede k speichern, wie viele Zahlen weniger als ein Bit haben. Diese Nachschlagetabelle kann dann verwendet werden, um die Anzahl o von einem Bit f(i) zu finden.
Sobald wir diese Zahl kennen, subtrahieren wir den Nachschlagetabellenwert für diese Anzahl von Bits von i , was uns den Permutationsindex p für Zahlen mit der gegebenen Anzahl von 1 Bits zurücklässt. Obwohl ich in diesem Bereich keine Forschung betrieben habe, bin ich ziemlich sicher, dass es eine Methode gibt, um die p-te Permutation von std::vector<bool> zu finden, die mit Nullen und o eins in den niedrigsten Bits initialisiert wird.
Auch hier hilft die Lookup-Tabelle. Wir können die Anzahl der vorhergehenden Zahlen mit weniger als einem Bit direkt berechnen, indem wir die einen Bits in der Eingangs-Ganzzahl zählen und in der Nachschlagetabelle lesen. Dann müssen Sie "nur" den Permutationsindex bestimmen und zu dem nachgeschlagenen Wert hinzufügen, und Sie sind fertig.
Natürlich ist das nur ein grober Umriss und einige Teile (besonders die Permutationen) könnten länger dauern als es klingt.
Sie haben sich selbst gesagt
Ich versuche, dies zu verwenden, um einen großen Datensatz zu kennzeichnen und die Reihenfolge, in der ich sie suche, zu priorisieren.
Was für mich klingt, als ob Sie von der niedrigen Hamming-Distanz zur hohen Hamming-Distanz gehen würden. In diesem Fall würde es ausreichen, eine inkrementelle Version zu haben, die die nächste Nummer aus dem vorherigen erzeugt:
%Vor% Natürlich funktioniert std::next_permutation permutation nicht so, aber ich denke, es ist klar, wie ich es benutzen will.