Frage Warum druckt dieser Code, der zufällige Zeichenfolgen verwendet, "Hallo Welt"?


Die folgende Druckanweisung würde "Hallo Welt" drucken. Könnte das jemand erklären?

System.out.println(randomString(-229985452) + " " + randomString(-147909649));

Und randomString() sieht aus wie das:

public static String randomString(int i)
{
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    while (true)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char)('`' + k));
    }

    return sb.toString();
}

1588
2018-03-03 04:38


Ursprung


Antworten:


Wenn eine Instanz von java.util.Random wird mit einem spezifischen Seed-Parameter konstruiert (in diesem Fall -229985452 oder -147909649), folgt der Algorithmus zur Generierung von Zufallszahlen Anfang mit diesem Startwert.

Jeden Random konstruiert mit dem gleichen Samen wird jedes Mal das gleiche Zahlenmuster erzeugen.


844
2018-03-03 04:40



Die anderen Antworten erklären warum, aber hier ist wie.

Gegeben eine Instanz von Random:

Random r = new Random(-229985452)

Die ersten 6 Zahlen, die r.nextInt(27) erzeugt werden:

8
5
12
12
15
0

und die ersten 6 Zahlen, die r.nextInt(27) erzeugt gegeben Random r = new Random(-147909649) sind:

23
15
18
12
4
0

Dann fügen Sie diese Zahlen einfach zur Ganzzahldarstellung des Zeichens hinzu ` (was 96 ist):

8  + 96 = 104 --> h
5  + 96 = 101 --> e
12 + 96 = 108 --> l
12 + 96 = 108 --> l
15 + 96 = 111 --> o

23 + 96 = 119 --> w
15 + 96 = 111 --> o
18 + 96 = 114 --> r
12 + 96 = 108 --> l
4  + 96 = 100 --> d

1084
2018-03-03 04:55



Ich werde es hier lassen. Wer viel (CPU-) Zeit übrig hat, kann frei experimentieren :) Auch wenn Sie einige fork-join-fu gemeistert haben, damit dieses Ding alle CPU-Kerne verbrennt (nur Threads sind langweilig, oder?), Teilen Sie es bitte mit dein Code. Ich würde es sehr begrüßen.

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    generate("stack");
    generate("over");
    generate("flow");
    generate("rulez");

    System.out.println("Took " + (System.currentTimeMillis() - time) + " ms");
}

private static void generate(String goal) {
    long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE);
    System.out.println(seed[0]);
    System.out.println(randomString(seed[0], (char) seed[1]));
}

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);

        for (int i = 0; i < input.length; i++)
            pool[i] = (char) random.nextInt(27);

        if (random.nextInt(27) == 0) {
            int base = input[0] - pool[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] - pool[i] != base)
                    continue label;
            }
            return new long[]{seed, base};
        }

    }

    throw new NoSuchElementException("Sorry :/");
}

public static String randomString(long i, char base) {
    System.out.println("Using base: '" + base + "'");
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    for (int n = 0; ; n++) {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char) (base + k));
    }

    return sb.toString();
}

Ausgabe:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms

262
2018-03-03 15:03



Jeder hier hat eine großartige Arbeit geleistet, zu erklären, wie der Code funktioniert und zu zeigen, wie man seine eigenen Beispiele erstellen kann, aber hier ist eine informationstheoretische Antwort, die zeigt, warum wir vernünftigerweise eine Lösung erwarten können, die die Brute-Force-Suche letztendlich finden wird.

Die 26 verschiedenen Kleinbuchstaben bilden unser Alphabet Σ. Um Wörter mit unterschiedlichen Längen erzeugen zu können, fügen wir ferner ein Terminator-Symbol hinzu  um ein erweitertes Alphabet zu erhalten Σ' := Σ ∪ {⊥}.

Lassen α Sei ein Symbol und X eine gleichmäßig verteilte Zufallsvariable über Σ'. Die Wahrscheinlichkeit, dieses Symbol zu erhalten, P(X = α)und sein Informationsgehalt, I(α), sind gegeben durch:

P (X = α) = 1 / | Σ '| = 1/27

I (α) = -log & sub2; [P (X = α)] = -log & sub2; (1/27) = log & sub2; (27)

Für ein Wort ω ∈ Σ* und sein ⊥-abgeschlossenes Gegenstück ω' := ω · ⊥ ∈ (Σ')*, wir haben

I (ω): = I (ω ') = | ω' | * log & sub2; (27) = (| & omega; + 1) * log & sub2; (27)

Da der Pseudozufallszahlengenerator (PRNG) mit einem 32-Bit-Startwert initialisiert wird, können wir die meisten Wörter der Länge bis zu erwarten

λ = Boden [32 / log & sub2; (27)] - 1 = 5

von mindestens einem Samen erzeugt werden. Selbst wenn wir nach einem 6-stelligen Wort suchen würden, wären wir immer noch 41.06% der Zeit erfolgreich. Nicht zu schäbig.

Für 7 Buchstaben sehen wir näher bei 1,52%, aber das habe ich nicht erkannt, bevor ich es versucht habe:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rng(631647094);
    std::uniform_int_distribution<char> dist('a', 'z' + 1);

    char alpha;
    while ((alpha = dist(rng)) != 'z' + 1)
    {
        std::cout << alpha;
    }
}

Siehe die Ausgabe: http://ideone.com/JRGb3l


248
2018-03-04 09:49



Ich habe ein schnelles Programm geschrieben, um diese Samen zu finden:

import java.lang.*;
import java.util.*;
import java.io.*;

public class RandomWords {
    public static void main (String[] args) {
        Set<String> wordSet = new HashSet<String>();
        String fileName = (args.length > 0 ? args[0] : "/usr/share/dict/words");
        readWordMap(wordSet, fileName);
        System.err.println(wordSet.size() + " words read.");
        findRandomWords(wordSet);
    }

    private static void readWordMap (Set<String> wordSet, String fileName) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(fileName));
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim().toLowerCase();
                if (isLowerAlpha(line)) wordSet.add(line);
            }
        }
        catch (IOException e) {
            System.err.println("Error reading from " + fileName + ": " + e);
        }
    }

    private static boolean isLowerAlpha (String word) {
        char[] c = word.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] < 'a' || c[i] > 'z') return false;
        }
        return true;
    }

    private static void findRandomWords (Set<String> wordSet) {
        char[] c = new char[256];
        Random r = new Random();
        for (long seed0 = 0; seed0 >= 0; seed0++) {
            for (int sign = -1; sign <= 1; sign += 2) {
                long seed = seed0 * sign;
                r.setSeed(seed);
                int i;
                for (i = 0; i < c.length; i++) {
                    int n = r.nextInt(27);
                    if (n == 0) break;
                    c[i] = (char)((int)'a' + n - 1);
                }
                String s = new String(c, 0, i);
                if (wordSet.contains(s)) {
                    System.out.println(s + ": " + seed);
                    wordSet.remove(s);
                }
            }
        }
    }
}

Ich habe es jetzt im Hintergrund laufen lassen, aber es hat schon genug Worte für ein klassisches Pangram gefunden:

import java.lang.*;
import java.util.*;

public class RandomWordsTest {
    public static void main (String[] args) {
        long[] a = {-73, -157512326, -112386651, 71425, -104434815,
                    -128911, -88019, -7691161, 1115727};
        for (int i = 0; i < a.length; i++) {
            Random r = new Random(a[i]);
            StringBuilder sb = new StringBuilder();
            int n;
            while ((n = r.nextInt(27)) > 0) sb.append((char)('`' + n));
            System.out.println(sb);
        }
    }
}

(Demo auf ideone.)

Ps. -727295876, -128911, -1611659, -235516779.


65
2018-03-03 18:33



Ich war fasziniert von diesem, ich lief diesen zufälligen Wortgenerator auf einer Wörterbuchwortliste. Bereich: Integer.MIN_VALUE zu Integer.MAX_VALUE

Ich habe 15131 Treffer.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

Drucke

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



Die meisten Zufallszahlengeneratoren sind tatsächlich "pseudozufällig". Sie sind Linear Congruential Generators oder LCGs (http://en.wikipedia.org/wiki/Linear_congruental_generator)

LCGs sind bei gegebenem Saatgut recht vorhersehbar. Verwenden Sie im Grunde einen Seed, der Ihnen Ihren ersten Buchstaben gibt, und schreiben Sie eine App, die fortfährt, den nächsten int (char) zu generieren, bis Sie den nächsten Buchstaben in Ihrer Zielzeichenfolge eingeben und notieren, wie oft Sie die LCG aufrufen mussten. Fahren Sie fort, bis Sie jeden einzelnen Buchstaben generiert haben.


26
2018-03-04 10:59



Zufällig gibt immer dieselbe Sequenz zurück. Es wird zum Mischen von Arrays und anderen Operationen als Permutationen verwendet.

Um verschiedene Sequenzen zu erhalten, muss die Sequenz in einer Position initialisiert werden, die "Seed" genannt wird.

Das randomSting erhält die Zufallszahl in der i-Position (seed = -229985452) der "random" -Sequenz. Dann benutzt das ASCII Code für die nächsten 27 Zeichen in der Sequenz nach der Startposition, bis dieser Wert gleich 0 ist. Dies gibt das "Hallo" zurück. Die gleiche Operation wird für "Welt" durchgeführt.

Ich denke, dass der Code für keine anderen Wörter funktioniert hat. Der Typ, der programmiert hat, kennt die Zufallssequenz sehr gut.

Es ist ein sehr guter Geek-Code!


22
2018-03-03 04:54