java - utils - Perché questo codice che utilizza stringhe casuali stampa "ciao mondo"?




random string utils java (10)

Casuale restituisce sempre la stessa sequenza. È usato per mischiare matrici e altre operazioni come permutazioni.

Per ottenere sequenze diverse, è necessario inizializzare la sequenza in una posizione, chiamata "seme".

Il randomSting ottiene il numero casuale nella posizione i (seed = -229985452) della sequenza "random". Quindi usa il codice ASCII per il prossimo 27 carattere nella sequenza dopo la posizione di seme fino a quando questo valore è uguale a 0. Questo restituisce "Ciao". La stessa operazione viene eseguita per "mondo".

Penso che il codice non ha funzionato per altre parole. Il ragazzo che ha programmato che conosce molto bene la sequenza casuale.

È un ottimo codice per il geek!

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

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

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

Dai documenti Java, questa è una caratteristica intenzionale quando si specifica un valore seme per la classe Random.

Se due istanze di Random vengono create con lo stesso seme e viene creata la stessa sequenza di chiamate di metodo per ognuna, genereranno e restituiranno sequenze identiche di numeri. Per garantire questa proprietà, sono specificati algoritmi particolari per la classe Random. Le implementazioni Java devono utilizzare tutti gli algoritmi mostrati qui per la classe Random, a fini di assoluta portabilità del codice Java.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html

Tuttavia, si potrebbe pensare che ci siano impliciti problemi di sicurezza nell'avere numeri "casuali" prevedibili.


Ecco un piccolo miglioramento per la answer Denis Tulskiy. Dimezza il tempo

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();

    int[] dif = new int[input.length - 1];
    for (int i = 1; i < input.length; i++) {
        dif[i - 1] = input[i] - input[i - 1];
    }

    mainLoop:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);
        int lastChar = random.nextInt(27);
        int base = input[0] - lastChar;
        for (int d : dif) {
            int nextChar = random.nextInt(27);
            if (nextChar - lastChar != d) {
                continue mainLoop;
            }
            lastChar = nextChar;
        }
        if(random.nextInt(27) == 0){
            return new long[]{seed, base};
        }
    }

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

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 .


La maggior parte dei generatori di numeri casuali sono, in effetti, "pseudo casuali". Sono generatori lineari congruenti 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.


Le altre risposte spiegano perché, ma ecco come.

Data un'istanza di Random :

Random r = new Random(-229985452)

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

8
5
12
12
15
0

e i primi 6 numeri che r.nextInt(27) genera in Random r = new Random(-147909649) sono:

23
15
18
12
4
0

Quindi aggiungi questi numeri alla rappresentazione intera del carattere ` (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

Poiché la multi-threading è molto semplice con Java, ecco una variante che cerca una seed utilizzando tutti i core disponibili: http://ideone.com/ROhmTA

import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;

public class SeedFinder {

  static class SearchTask implements Callable<Long> {

    private final char[] goal;
    private final long start, step;

    public SearchTask(final String goal, final long offset, final long step) {
      final char[] goalAsArray = goal.toCharArray();
      this.goal = new char[goalAsArray.length + 1];
      System.arraycopy(goalAsArray, 0, this.goal, 0, goalAsArray.length);
      this.start = Long.MIN_VALUE + offset;
      this.step = step;
    }

    @Override
    public Long call() throws Exception {
      final long LIMIT = Long.MAX_VALUE - this.step;
      final Random random = new Random();
      int position, rnd;
      long seed = this.start;

      while ((Thread.interrupted() == false) && (seed < LIMIT)) {
        random.setSeed(seed);
        position = 0;
        rnd = random.nextInt(27);
        while (((rnd == 0) && (this.goal[position] == 0))
                || ((char) ('`' + rnd) == this.goal[position])) {
          ++position;
          if (position == this.goal.length) {
            return seed;
          }
          rnd = random.nextInt(27);
        }
        seed += this.step;
      }

      throw new Exception("No match found");
    }
  }

  public static void main(String[] args) {
    final String GOAL = "hello".toLowerCase();
    final int NUM_CORES = Runtime.getRuntime().availableProcessors();

    final ArrayList<SearchTask> tasks = new ArrayList<>(NUM_CORES);
    for (int i = 0; i < NUM_CORES; ++i) {
      tasks.add(new SearchTask(GOAL, i, NUM_CORES));
    }

    final ExecutorService executor = Executors.newFixedThreadPool(NUM_CORES, new ThreadFactory() {

      @Override
      public Thread newThread(Runnable r) {
        final Thread result = new Thread(r);
        result.setPriority(Thread.MIN_PRIORITY); // make sure we do not block more important tasks
        result.setDaemon(false);
        return result;
      }
    });
    try {
      final Long result = executor.invokeAny(tasks);
      System.out.println("Seed for \"" + GOAL + "\" found: " + result);
    } catch (Exception ex) {
      System.err.println("Calculation failed: " + ex);
    } finally {
      executor.shutdownNow();
    }
  }
}

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

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


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 

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 ottenere un alfabeto esteso Σ' := Σ ∪ {⊥} .

Sia α un simbolo e X una variabile casuale uniformemente distribuita su Σ' . 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 la sua controparte terminata ω' := ω · ⊥ ∈ (Σ')* , 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





random