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

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

Dado un ejemplo 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

Entonces simplemente 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

Lo dejaré aquí. Quien tenga mucho tiempo (CPU) de sobra, siéntase libre de experimentar:) Además, si ha dominado algún fork-join-fu para hacer que esta cosa queme todos los núcleos de CPU (solo los hilos son aburridos, ¿verdad?), por favor comparta su código. Se lo agradecería mucho.

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

Todos aquí hicieron un gran trabajo explicando cómo funciona el código y mostrando 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 la generación de palabras de diferentes longitudes, añadimos un símbolo terminador ⊥ para obtener un alfabeto extendido Σ' := Σ ∪ {⊥}.

Let α ser un símbolo y X una variable aleatoria uniformemente distribuida sobre Σ'. La probabilidad de obtener ese símbolo, P(X = α), y su contenido de información, I(α), están dadas 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)

Desde el Número Pseudoaleatorio Generator (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

Para ser generado por al menos una semilla. Incluso si buscáramos una palabra de 6 caracteres, todavía tendríamos éxito alrededor del 41.06% de las veces. No está mal.

Para 7 letras estamos mirando más cerca de 1.52%, pero no me había dado cuenta de que antes de darle una oportunidad:

#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

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 corriendo en segundo plano ahora, pero ya ha encontrado suficientes palabras para un pangram 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.)

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

Estaba intrigado por esto, corrí este generador de palabras aleatorias 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) + " ");
}

Imprime

the quick browny fox jumps over a lazy dog 

La mayoría de los generadores de números aleatorios son, de hecho, "pseudo aleatorios."Son Generadores Lineales Congruenciales, o LCGs ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Las 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 anote cuántas veces tuvo que invocar el LCG. Continúa hasta que hayas generado todas y cada una de las letras.

Random siempre devuelve la misma secuencia. Se utiliza para barajar arrays y otras operaciones como permutaciones.

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

El randomSting obtiene el número aleatorio en la posición i (seed = -229985452) de la secuencia "aleatoria". Luego usa el código ASCII para el siguiente carácter 27 en la secuencia después de la posición de semilla hasta que este valor sea igual a 0. Esto devuelve el "hola". La misma operación se hace para "mundo".

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

Es un gran código friki!

Como multi-threading es muy fácil con Java, aquí hay una variante que busca una semilla usando 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();
    }
  }
}

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 :/");
}

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

De los documentos de Java, esta es una característica intencional cuando se especifica un valor de semilla para la clase aleatoria.

Si se crean dos instancias de Random con la misma semilla, y misma secuencia de llamadas de método se hace para cada uno, se generarán y devuelve secuencias idénticas de números. Para garantizar esto propiedad, algoritmos particulares se especifican para la clase Random. Las implementaciones de Java deben usar todos los algoritmos que se muestran aquí para clase aleatoria, para el bien de la portabilidad absoluta del código Java.

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

Sin embargo, es extraño pensar que hay problemas de seguridad implícitos en tener números 'aleatorios' predecibles.

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

Aquí hay una mejora menor 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 :/");
}