¿Por qué este código que usa cadenas aleatorias imprime "hola mundo"?

1769

La siguiente declaración de impresión imprimiría "hola mundo". ¿Alguien podría explicar esto?

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

Y se randomString()ve así:

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();
}
0x56794E
fuente
158
Bueno, esas semillas en particular funcionan perfectamente. Aleatorio no es realmente aleatorio, es seudoaleatorio.
tckmn
341
Funciona, como han dicho otros, porque el azar no lo es. Para mí, una pregunta más interesante sería la persona que escribió eso, la fuerza bruta, o hay una manera fácil de predecir qué aleatorio generaría para los próximos valores de N para una semilla dada. El forzamiento bruto es fácil y con el hardware moderno no debería llevar mucho tiempo, por lo que fue una forma viable de hacerlo. Dado que es estático, incluso podría distribuir fácilmente la búsqueda a través de una red.
jmoreno
78
Me pregunto el propósito de nen for (int n = 0; ; n++). Podrían usar for(;;)o en su while(true)lugar!
Eng.Fouad
13
En una secuencia verdaderamente aleatoria, eventualmente aparecerá cada cadena posible. En una secuencia pseudoaleatoria de alta calidad, puede esperar razonablemente cada posible cadena de longitud (log_s (N) - n) bits (donde N es el número de bits en el estado interno de PRNG yn es un número pequeño, elija 8 por conveniencia) ) para aparecer en el ciclo. Este código recibe ayuda del uso de un punto de inicio codificado libremente elegido (el valor del carácter de retroceso de caracteres) que recupera casi la totalidad de los 8 bits.
dmckee --- ex-gatito moderador
13
Esto es de una publicación que escribí hace un par de años. vanillajava.blogspot.co.uk/2011/10/randomly-no-so-random.html
Peter Lawrey

Respuestas:

917

Cuando java.util.Randomse construye una instancia de con un parámetro semilla específico (en este caso -229985452o -147909649), sigue el algoritmo de generación de números aleatorios que comienza con ese valor semilla.

Cada Randomconstruido con la misma semilla generará el mismo patrón de números cada vez.

FThompson
fuente
8
@Vulcan: el javadoc dice que la semilla es de 48 bits. docs.oracle.com/javase/7/docs/api/java/util/Random.html . Y además, las semillas reales son valores de 32 bits.
Stephen C
80
Cada elemento de la secuencia de números aleatorios se toma el módulo 27, y hay 6 elementos en cada uno de "hello\0"y "world\0". Si asumió un generador verdaderamente aleatorio, las probabilidades serían de 1 en 27 ^ 6 (387,420,489) de obtener la secuencia que estaba buscando, por lo que es bastante impresionante, ¡pero no alucinante!
Russell Borogove
17
@RussellBorogove: Pero con esas probabilidades, y 2 ^ 64 semillas posibles, se esperan 47,6 mil millones de valores de semillas que dan esa secuencia. Es solo cuestión de encontrar uno.
dan04
8
@ dan04: no estaba muy dispuesto a hacer esa estimación; dependiendo de la implementación del PRNG, el tamaño de la palabra semilla puede no ser igual al tamaño del estado, y las rutas de secuencia pueden no estar distribuidas de manera uniforme. Pero aún así, las probabilidades son definitivamente buenas, y si no puedes encontrar un par, puedes intentarlo nuevamente con una carcasa diferente ( "Hello" "World"), o usar en 122-klugar de 96+k, o ...
Russell Borogove
77
@ ThorbjørnRavnAndersen El Javadoc especifica que "se especifican algoritmos particulares para la clase Random. Las implementaciones Java deben usar todos los algoritmos que se muestran aquí para la clase Random, en aras de la portabilidad absoluta del código Java".
FThompson
1137

Las otras respuestas explican por qué, pero aquí es cómo.

Dada una instancia de Random:

Random r = new Random(-229985452)

Los primeros 6 números que r.nextInt(27)genera son:

8
5
12
12
15
0

y los primeros 6 números que r.nextInt(27)genera dado Random r = new Random(-147909649)son:

23
15
18
12
4
0

Luego solo agregue esos números a la representación entera del carácter `(que es 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
Eng.Fouad
fuente
48
Pendientemente, new Random(-229985452).nextInt(27)siempre devuelve 8.
user253751
1
@immibis por qué? Me refiero a que Random () debería devolver un número aleatorio cada vez, ¿no un conjunto de números ordenado fijo?
roottraveller
55
@rootTraveller Para empezar, new Random()no devuelve ningún número en absoluto.
user253751
2
¿Hay alguna forma de calcular estas semillas? Debe haber alguna lógica ... o es solo fuerza bruta.
Sohit Gore
2
@SohitGore Dado que el valor predeterminado de Java Randomno es criptográficamente seguro (estoy bastante seguro de que es un Mersenne Twister, pero no me cite al respecto), probablemente sea posible retroceder desde "Quiero estos números" hasta "este es el semilla que usaría ". He hecho algo similar con el generador congruencial lineal C estándar.
Financia la demanda de Mónica el
280

Lo dejaré aquí. Quien tenga mucho tiempo (CPU) de sobra, siéntase libre de experimentar :) Además, si ha dominado algo de fork-join-fu para hacer que esto queme todos los núcleos de CPU (solo los hilos son aburridos, ¿verdad?), Comparta tu codigo. Me sería de gran aprecio.

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

Salida:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms
Denis Tulskiy
fuente
24
@OneTwoThree nextInt(27)significa dentro del rango [0, 26].
Eng.Fouad
30
@Vulcan La mayoría de las semillas están muy cerca del valor máximo, al igual que si selecciona números aleatorios entre 1 y 1000, la mayoría de los números que termina seleccionando tendrán tres dígitos. No es sorprendente, cuando lo piensas :)
Thomas
18
@Vulcan De hecho, si hace los cálculos, verá que están tan cerca del valor máximo como de cero (supongo que la semilla se interpreta como no firmada en el código de generación). Pero debido a que el número de dígitos crece solo logarítmicamente con el valor real, el número se ve muy cerca cuando realmente no lo es.
Thomas
10
Gran respuesta. Y para obtener puntos de bonificación, ¿puedes encontrar una semilla que inicialice un Aleatorio que produzca la secuencia de 4 semillas necesarias para la inicialización de los randoms finales?
Marek
13
@Marek: No creo que dioses de pseudoaleatorio aprueben tal comportamiento.
Denis Tulskiy
254

Todos aquí hicieron un gran trabajo al explicar cómo funciona el código y al mostrar cómo puedes construir tus propios ejemplos, pero aquí hay una respuesta teórica de información que muestra por qué podemos esperar razonablemente que exista una solución que la búsqueda de fuerza bruta eventualmente encontrará.

Las 26 letras minúsculas diferentes forman nuestro alfabeto Σ. Para permitir generar palabras de diferentes longitudes, agregamos un símbolo terminador para obtener un alfabeto extendido Σ' := Σ ∪ {⊥}.

Sea αun símbolo y X una variable aleatoria distribuida uniformemente Σ'. La probabilidad de obtener ese símbolo, P(X = α)y su contenido de información I(α), están dados por:

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

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

Para una palabra ω ∈ Σ*y su ⊥-contraparte terminada ω' := ω · ⊥ ∈ (Σ')*, tenemos

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

Dado que el generador de números pseudoaleatorios (PRNG) se inicializa con una semilla de 32 bits, podemos esperar la mayoría de las palabras de longitud hasta

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

ser generado por al menos una semilla. Incluso si buscáramos una palabra de 6 caracteres, tendríamos éxito aproximadamente el 41.06% del tiempo. No está nada mal.

Para 7 letras, estamos mirando más cerca del 1,52%, pero no me había dado cuenta antes de intentarlo:

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

Ver la salida: http://ideone.com/JRGb3l

xDD
fuente
mi teoría de la información es algo débil pero me encanta esta prueba. ¿Alguien puede explicarme la línea lambda, claramente estamos dividiendo el contenido de información de uno con el otro, pero por qué esto nos da nuestra longitud de palabra? como ya he dicho que estoy un poco oxidada por lo disculpas por preguntar lo obvio (NB es algo que ver con la salida código -desde límite de Shannon)
Mike HR
1
@ MikeH-R La línea lambda es la I(⍵)ecuación reordenada. I(⍵)es 32 (bits) y |⍵|resulta ser 5 (símbolos).
Iceman
67

Escribí un programa rápido para encontrar estas semillas:

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

Lo tengo ejecutándose en segundo plano ahora, pero ya ha encontrado suficientes palabras para un pangrama clásico:

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

PD. -727295876, -128911, -1611659, -235516779.

Ilmari Karonen
fuente
35

Estaba intrigado por esto, ejecuté este generador de palabras al azar en una lista de palabras del diccionario. Rango: Integer.MIN_VALUE a Integer.MAX_VALUE

Tengo 15131 visitas.

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

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

Huellas dactilares

the quick browny fox jumps over a lazy dog 
Puru--
fuente
77
Hiciste mi día hombre: DI lo probó con Long.Min / Max y buscó nombres de mis colegas y solo encontré a peter: (peter 4611686018451441623 peter 24053719 peter -4611686018403334185 peter -9223372036830722089 peter -461168684517906248127 peter 52119333339 peter 4611686017645756173 peter 781631731 peter 4611686019209019635 peter -9223372036073144077 peter -4611686017420317288 peter 1007070616 peter -9223372035847705192)
Marcel
25

La mayoría de los generadores de números aleatorios son, de hecho, "pseudoaleatorios". Son generadores congruenciales lineales o LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Los LCG son bastante predecibles dada una semilla fija. Básicamente, use una semilla que le dé su primera letra, luego escriba una aplicación que continúe generando el siguiente int (char) hasta que toque la siguiente letra en su cadena de destino y escriba cuántas veces tuvo que invocar el LCG. Continúa hasta que hayas generado todas y cada una de las letras.

Sinclair Schuller
fuente
3
¿Cuál es un ejemplo de un generador de números aleatorios no seudo
chiliNUT
1
@chiliNUT Tales generadores son dispositivos externos. Alguna lámpara electrónica. O bit mal escrito que se lee 0 o 1. No se puede hacer un generador digital puro de números aleatorios, los algoritmos digitales NO son aleatorios, son absolutamente precisos.
Gangnus
@chiliNUT Muchos sistemas operativos recopilan entropía . Por ejemplo, en Linux puede usar el /dev/urandomdispositivo para leer datos aleatorios. Sin embargo, este es un recurso escaso. Por lo tanto, estos datos aleatorios se utilizan normalmente para sembrar PRNG.
Adrian W
@AdrianW Wikipedia dice urandomque todavía es pseudoaleatorio en.wikipedia.org/wiki//dev/random
chiliNUT
1
Sí, pero es criptográficamente seguro, lo que significa que uno no puede realizar ataques de fuerza bruta (como encontrar la semilla de la secuencia "aleatoria" "hola mundo") con secuencias aleatorias creadas a partir de /dev/random. El artículo que cité anteriormente dice que el kernel de Linux genera entropía a partir de los tiempos del teclado, los movimientos del mouse y los tiempos IDE y hace que los datos de caracteres aleatorios estén disponibles para otros procesos del sistema operativo a través de los archivos especiales / dev / random y / dev / urandom. Eso me deja creer que es realmente al azar. Puede ser que eso no sea completamente correcto. Pero /dev/randomal menos contiene algo de entropía.
Adrian W
23

Como el subprocesamiento múltiple es muy fácil con Java, aquí hay una variante que busca una semilla utilizando todos los núcleos disponibles: 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();
    }
  }
}
TwoThe
fuente
Para java noob como yo, necesita sufijar el número de salida con Ly cambiar el tipo de argumento a long, es decir randomString(long i), para jugar. :)
Fruta
21

Aleatorio siempre devuelve la misma secuencia. Se utiliza para barajar matrices y otras operaciones como permutaciones.

Para obtener diferentes secuencias, es necesario inicializar la secuencia en alguna posición, llamada "semilla".

RandomSting obtiene el número aleatorio en la posición i (seed = -229985452) de la secuencia "aleatoria". Luego usa el código ASCII para los siguientes 27 caracteres en la secuencia después de la posición inicial hasta que este valor sea igual a 0. Esto devuelve el "hola". La misma operación se realiza para "mundo".

Creo que el código no funcionó para otras palabras. El tipo que programó que conoce muy bien la secuencia aleatoria.

¡Es un código geek muy bueno!

Arnaldo Ignacio Gaspar Véjar
fuente
10
Dudo que él "conozca muy bien la secuencia aleatoria". Lo más probable es que haya probado miles de millones de posibles semillas hasta encontrar una que funcione.
dan04
24
@ dan04 Los programadores reales no solo usan el PRNG, sino que recuerdan todo el período de memoria y enumeran los valores según sea necesario.
Thomas
1
"Aleatorio siempre devuelve la misma secuencia" - poner () después de Aleatorio o mostrarlo como un código. De lo contrario, la oración es falsa.
Gangnus
14

El principal es la clase aleatoria construida con la misma semilla que generará el mismo patrón de números cada vez.

tomj0101
fuente
12

Derivado de la respuesta de Denis Tulskiy , este método genera la semilla.

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) {
                for (int i = 0; i < input.length; i++) {
                    if (input[i] != pool[i])
                        continue label;
                }
                return seed;
            }

        }

    throw new NoSuchElementException("Sorry :/");
}
sulai
fuente
10

Desde los documentos de Java, esta es una característica intencional cuando se especifica un valor de inicialización para la clase Random.

Si se crean dos instancias de Aleatorio con la misma semilla, y se realiza la misma secuencia de llamadas a métodos para cada una, generarán y devolverán secuencias idénticas de números. Para garantizar esta propiedad, se especifican algoritmos particulares para la clase Random. Las implementaciones de Java deben usar todos los algoritmos que se muestran aquí para la clase Random, en aras de la portabilidad absoluta del código Java.

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

Aunque extraño, pensaría que hay problemas de seguridad implícitos al tener números 'aleatorios' predecibles.

escritura02392
fuente
3
Es por eso que el constructor predeterminado de Random"establece la semilla del generador de números aleatorios en un valor muy probable que sea distinto de cualquier otra invocación de este constructor" ( javadoc ). En la implementación actual, esta es una combinación de la hora actual y un contador.
Martin
En efecto. Presumiblemente, hay casos de uso prácticos para especificar el valor inicial de la semilla, entonces. Supongo que es el principio de funcionamiento de los pseudo-llaves vía radio se puede obtener (los RSA?)
deed02392
44
@ deed02392 Por supuesto, hay casos de uso prácticos para especificar un valor de inicialización. Si está simulando datos para usar algún tipo de enfoque de Monte Carlo para resolver un problema, entonces es bueno poder reproducir sus resultados. Establecer una semilla inicial es la forma más fácil de hacerlo.
Dason
8

Se trata de "semilla". Las mismas semillas dan el mismo resultado.

Burak Keceli
fuente
3

Aquí hay una pequeña mejora para la respuesta de Denis Tulskiy . Reduce el tiempo a la mitad

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 :/");
}
Ilya Gazman
fuente
1

Se trata de la semilla de entrada . La misma semilla da los mismos resultados todo el tiempo. Incluso si vuelve a ejecutar su programa una y otra vez, es el mismo resultado.

public static void main(String[] args) {

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

}

private static void randomString(int i) {
    Random ran = new Random(i);
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());

}

Salida

-755142161
-1073255141
-369383326
1592674620
-1524828502
------------
-755142161
-1073255141
-369383326
1592674620
-1524828502
nagendra547
fuente