Frage Generiere eine zufällige Folge von ganzen Zahlen, die sich um 1 Bit ohne Wiederholungen unterscheiden


Ich muss eine (Pseudo) zufällige Folge von N-Bit-Ganzzahlen erzeugen, wobei aufeinanderfolgende ganze Zahlen sich von der vorherigen um nur 1 Bit unterscheiden, und die Sequenz wird niemals wiederholt. Ich weiß, dass ein Gray-Code sich nicht wiederholende Sequenzen mit nur 1 Bit Unterschied erzeugt, und ein LFSR wird sich nicht wiederholende, zufällige Sequenzen erzeugen, aber ich bin nicht sicher, wie ich diese Ideen kombinieren kann, um das zu erzeugen, was ich will.

Praktisch wird N sehr groß sein, sagen wir 1000. Ich möchte diesen großen Raum von 2 ^ 1000 ganzen Zahlen zufällig abtasten, aber ich muss etwas wie einen zufälligen Gang erzeugen, weil die Anwendung im Verstand nur von einer Zahl zur nächsten springen kann ein bisschen kippen.


6
2018-06-11 18:44


Ursprung


Antworten:


Verwenden Sie einen beliebigen Zufallsgenerator, um eine Ganzzahl zwischen 1 und N (oder 0 bis N-1 abhängig von der Sprache) zu generieren. Verwenden Sie das Ergebnis, um den Index des zu spiegelnden Bits zu bestimmen.

Um Zufälligkeit zu befriedigen, müssen Sie zuvor generierte Zahlen speichern (danke ShreevatsaR). Darüber hinaus können Sie auf ein Szenario stoßen, in dem keine sich nicht wiederholenden Antworten möglich sind, so dass dies auch einen Backtracking-Algorithmus erfordert.


5
2018-06-11 18:51



Das lässt mich an Fraktale denken - an eine Grenze in einem Julia-Set oder etwas in dieser Richtung.

Wenn N 1000 ist, verwende eine 2 ^ 500 x 2 ^ 500 Fraktal-Bitmap (erzeuge sie natürlich nicht im Voraus - du kannst jedes Pixel nach Bedarf ableiten und die meisten werden nicht benötigt). Jede Pixelbewegung ist ein Pixel nach oben, unten, links oder rechts folgend der Grenzlinie zwischen Pixeln, wie ein einfacher Bitmap-Tracing-Algorithmus. Solange Sie am Rand der Bitmap beginnen, sollten Sie früher oder später an den Rand der Bitmap zurückkehren. Wenn Sie einer bestimmten "Farb" -Begrenzung folgen, sollte immer eine geschlossene Kurve ohne Selbstkreuzungen angezeigt werden Version dieses Fraktals.

Die x- und y-Achsen der Bitmap benötigen natürlich "Gray-codierte" Koordinaten - ein bisschen wie übergroße Karnaugh-Karten. Jeder Schritt in der Verfolgung (ein Pixel nach oben, unten, links oder rechts) entspricht einer Ein-Bit-Änderung in einer Bitmap-Koordinate und daher in einem Bit der resultierenden Werte in dem Random Walk.

BEARBEITEN

Ich habe gerade festgestellt, dass es ein Problem gibt. Je runzeliger die Grenze ist, desto wahrscheinlicher ist es, dass Sie in der Spur einen Punkt treffen, an dem Sie eine Richtung wählen können, z. B. ...

 * | .
---+---
 . | *

In welche Richtung Sie diesen Punkt eingeben, Sie haben die Wahl zwischen drei Auswegen. Wählen Sie das falsche der beiden anderen und Sie können zu diesem Punkt zurückkehren, daher ist dies ein möglicher Selbstkreuzungspunkt und mögliche Wiederholung. Sie können die Option "In die gleiche Richtung fortsetzen" aufheben, unabhängig davon, auf welchem ​​Weg Sie beim Abfahren die gleichen Begrenzungsfarben links und rechts neben Ihrem Grenzpfad beibehalten. Dabei bleiben jedoch zwei Richtungen übrig.

ich denken Das Problem kann beseitigt werden, indem im Fraktal mindestens drei Farben erzeugt werden und immer die gleiche Farbe an einer bestimmten Seite (relativ zur Spurrichtung) der Grenze beibehalten wird. Es kann jedoch auch einen "solange das Fraktal nicht zu runzelig ist" gelten.

Der letzte Ausweg besteht darin, eine Liste der Punkte zu führen, an denen diese Auswahl verfügbar war. Wenn Sie zum selben Punkt zurückkehren, gehen Sie zurück und nehmen Sie die andere Alternative.


1
2018-06-11 21:50



Während ein Algorithmus wie folgt:

seed()
i = random(0, n)
repeat:
    i ^= >> (i % bitlen)
    yield i

... würde eine zufällige Folge von ganzen Zahlen, die sich jeweils um 1 Bit unterscheiden, zurückgeben, es würde ein riesiges Array für Backtracing erfordern, um die Eindeutigkeit der Zahlen sicherzustellen. Außerdem erhöht sich Ihre Laufzeit exponentiell (?) Mit zunehmender Dichte Ihres Backtrace, da die Wahrscheinlichkeit, eine neue und sich nicht wiederholende Zahl zu treffen, mit jeder Zahl in der Sequenz abnimmt.

Um Zeit und Raum zu reduzieren, könnte man versuchen, eines davon zu integrieren:

Bloom-Filter

Benutze einen Bloom-Filter um den Platz (und die Zeit), die für das Eindeutigkeits-Backtracing benötigt werden, drastisch zu reduzieren.

Wie Bloom-Filter haben den Nachteil, von Zeit zu Zeit eine gewisse Rate falsch detektierter Wiederholungen falsch-positiv zu produzieren (sic!) (die also übersprungen werden) würde in Ihrer Sequenz auftreten.

Während die Verwendung von a Bloom-Filter würde den Raum und die Zeit reduzieren, würde Ihre Laufzeit noch exponentiell (?) steigen ...

Hilbert-Kurve

EIN Hilbert-Kurve repräsentiert eine Nicht-Wiederholung (Art von Pseudo-Zufall) gehe auf einer quadratischen Ebene (oder in einem Würfel), wobei jeder Schritt die Länge 1 hat.
Verwendung einer Hilbert-Kurve (bei einer geeigneten Verteilung von Werten) könnte man die Notwendigkeit eines Backtrace vollständig beseitigen. Um zu ermöglichen, dass deine Sequenz einen Samen erhält, den du generieren würdest n (n die Dimension deiner Ebene / Würfel / Hyperwürfel) Zufallszahlen zwischen 0 und s (s ist die Länge der Seiten deines Flugzeugs / Kubus / Hyperkubus). Nicht nur würde a Hilbert-Kurve Entfernen Sie die Notwendigkeit für ein Backtrace, es würde auch den Sequenzer laufen lassen O(1) pro Nummer (im Gegensatz zur Verwendung eines Backtrace, wodurch Ihre Laufzeit exponentiell (?) im Laufe der Zeit zunimmt ...)
Um Ihre Sequenz zu säen, würden Sie Ihre nDimensionale Verteilung durch zufällige Verschiebungen in jedem seiner n Abmessungen.


Ps: Sie könnten hier bessere Antworten erhalten: CSTheory @ StackExchange  (oder nicht, siehe Kommentare)


0
2018-06-11 21:44