Domanda Perché questo codice che utilizza stringhe casuali stampa "ciao mondo"?


La seguente dichiarazione di stampa dovrebbe stampare "Ciao mondo". Qualcuno potrebbe spiegarlo?

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

E randomString() Somiglia a questo:

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


origine


risposte:


Quando un'istanza di java.util.Random è costruito con un parametro seme specifico (in questo caso -229985452 o -147909649), segue l'algoritmo di generazione del numero casuale inizio con quel valore di seme

Ogni Random costruito con lo stesso seme genererà sempre lo stesso modello di numeri.


844
2018-03-03 04:40



Le altre risposte spiegano perché, ma ecco come.

Data un'istanza di Random:

Random r = new Random(-229985452)

I primi 6 numeri che r.nextInt(27) genera sono:

8
5
12
12
15
0

e i primi 6 numeri che r.nextInt(27) generato dato Random r = new Random(-147909649) siamo:

23
15
18
12
4
0

Quindi aggiungi questi numeri alla rappresentazione intera del personaggio ` (che è 96):

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



Lo lascerò qui. Chiunque abbia un sacco di tempo (CPU) per risparmiare, sentiti libero di sperimentare :) Inoltre, se hai padroneggiato alcuni fork-join-fu per far sì che questa cosa masterizzi tutti i core della CPU (solo i thread sono noiosi, giusto?), Per favore condividi il tuo codice. Lo apprezzerei molto

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();
}

Produzione:

-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



Tutti qui hanno fatto un ottimo lavoro nel spiegare come funziona il codice e mostrare come è possibile costruire i propri esempi, ma ecco una risposta teorica che mostra perché possiamo ragionevolmente aspettarci che esista una soluzione che alla fine la ricerca forza bruta troverà.

Le 26 diverse lettere minuscole formano il nostro alfabeto Σ. Per consentire la generazione di parole di diversa lunghezza, aggiungiamo ulteriormente un simbolo di terminazione  per produrre un alfabeto esteso Σ' := Σ ∪ {⊥}.

Permettere α essere un simbolo e X una variabile casuale uniformemente distribuita sopra Σ'. La probabilità di ottenere quel simbolo, P(X = α)e il suo contenuto informativo, I(α), sono dati da:

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

I (α) = -log₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)

Per una parola ω ∈ Σ* e il suo ⊥-controparte terminata ω' := ω · ⊥ ∈ (Σ')*, noi abbiamo

I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)

Poiché il Pseudorandom Number Generator (PRNG) è inizializzato con un seme a 32 bit, possiamo aspettarci più parole di lunghezza fino a

λ = floor [32 / log₂ (27)] - 1 = 5

essere generato da almeno un seme. Anche se dovessimo cercare una parola di 6 caratteri, avremmo comunque successo circa il 41,06% delle volte. Non troppo malandato.

Per 7 lettere ci stiamo avvicinando all'1,52%, ma non me ne ero reso conto prima di provare:

#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;
    }
}

Vedi l'output: http://ideone.com/JRGb3l


248
2018-03-04 09:49



Ho scritto un programma rapido per trovare questi semi:

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);
                }
            }
        }
    }
}

Ce l'ho ora in esecuzione in background, ma ha già trovato abbastanza parole per un pangram classico:

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 su ideone.)

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


65
2018-03-03 18:33



Sono stato incuriosito da questo, ho eseguito questo generatore di parole casuali su una lista di parole del dizionario. Intervallo: Intero.MIN_VALORE a Integer.MAX_VALUE

Ho ottenuto 15131 colpi.

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

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

stampe

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



La maggior parte dei generatori di numeri casuali sono, in effetti, "pseudo casuali". Sono generatori a congruenza lineare o LCG (http://en.wikipedia.org/wiki/Linear_congruential_generator)

Gli LCG sono abbastanza prevedibili dato un seme fisso. In pratica, usa un seme che ti dà la tua prima lettera, quindi scrivi un'app che continua a generare il prossimo int (char) finché non colpisci la lettera successiva nella stringa di destinazione e scrivi quante volte hai dovuto richiamare il LCG. Continua finché non hai generato ogni singola lettera.


26
2018-03-04 10:59