Dlaczego ten kod za pomocą losowych ciągów drukuje "hello world"?

Inne odpowiedzi wyjaśniają dlaczego, ale oto jak.

Podany przykład Random:

Random r = new Random(-229985452)

Pierwsze 6 liczb, które r.nextInt(27) generuje to:

8
5
12
12
15
0

Oraz 6 pierwszych liczb, które r.nextInt(27) generuje Random r = new Random(-147909649) to:

23
15
18
12
4
0

Następnie dodaj te liczby do reprezentacji całkowitej znaku ` (czyli 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

Zostawię to tutaj. Kto ma dużo czasu (CPU) do stracenia, zapraszam do eksperymentowania :) Ponadto, jeśli opanowałeś jakiś fork-join-fu, aby to coś spalić wszystkie rdzenie CPU (tylko wątki są nudne, prawda?), proszę udostępnić swój kod. Byłbym bardzo wdzięczny.

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

Wyjście:

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

Wszyscy tutaj wykonali świetną robotę wyjaśniając, jak działa kod i pokazując, jak można konstruować własne przykłady, ale oto teoretyczna odpowiedź informacyjna pokazująca, dlaczego możemy rozsądnie oczekiwać rozwiązania, które w końcu znajdzie brute force search.

26 różnych małych liter tworzy nasz alfabet Σ. Aby umożliwić generowanie słów o różnej długości, dodajemy dodatkowo symbol Terminatora ⊥, aby uzyskać rozszerzony alfabet Σ' := Σ ∪ {⊥}.

Let α być symbolem, A X równomiernie rozłożoną zmienną losową na Σ'. Prawdopodobieństwo uzyskania tego symbolu, P(X = α), i jego treści informacyjnej, I(α), są podane przez:

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

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

Dla wyrazu ω ∈ Σ* i jego ⊥-zakończonego odpowiednika ω' := ω · ⊥ ∈ (Σ')* mamy

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

Od liczby Pseudorandomowej Generator (PRNG) jest inicjowany 32-bitowym ziarnem, możemy spodziewać się większości słów o długości do

Λ = podłoga[32 / log₂(27)] - 1 = 5

Do wygenerowania przez co najmniej jedno ziarno. Nawet gdybyśmy szukali 6-znakowego słowa, Nadal odnosilibyśmy sukcesy około 41,06% przypadków. Nie za bardzo.

Na 7 liter patrzymy bliżej 1,52% , ale nie zdawałem sobie z tego sprawy przed próbą:

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

Zobacz wyjście: http://ideone.com/JRGb3l

Napisałem szybki program, aby znaleźć te nasiona:

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

Mam go uruchomiony w tle teraz, ale to już znaleźć wystarczająco dużo słów dla klasycznego pangram:

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

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

Zaintrygowało mnie to, uruchomiłem ten generator losowych słów na liście słów słownika. Zakres: Integer.MIN_VALUE to Integer.MAX_VALUE

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

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

Druki

the quick browny fox jumps over a lazy dog 

Większość generatorów liczb losowych to w rzeczywistości "pseudo losowe."Są to liniowe Generatory Kongruencyjne, czyli LCGs (http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCG są dość przewidywalne, biorąc pod uwagę stały materiał siewny. Zasadniczo, użyj ziarna, które daje pierwszą literę, a następnie napisz aplikację, która nadal generuje następny int (char), aż trafisz na następną literę w ciągu docelowym i zapisz, ile razy trzeba było wywołać LCG. Kontynuuj, aż / align = "left" /

Losowe zawsze zwracają tę samą sekwencję. Służy do tasowania tablic i innych operacji jako permutacje.

Aby uzyskać różne sekwencje, konieczne jest zainicjowanie sekwencji w jakiejś pozycji, zwanej "ziarnem".

Losowy otrzymuje losową liczbę w pozycji i (seed = -229985452) sekwencji "losowej". Następnie używa kodu ASCII dla kolejnych 27 znaków w sekwencji po pozycji nasiennej, aż ta wartość będzie równa 0. To zwróć "cześć". Ta sama operacja jest wykonywana dla "świata".

Myślę, że kod nie działał dla innych słów. Facet, który zaprogramował, zna losową sekwencję bardzo dobrze.

It ' s very great geek code!

Ponieważ wielowątkowość jest bardzo łatwa w Javie, oto wariant, który wyszukuje ziarno przy użyciu wszystkich dostępnych rdzeni: 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();
    }
  }
}

Uzyskana z odpowiedzi Denis Tulskiy , ta metoda generuje ziarno.

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

Głównym jest losowa Klasa zbudowana z tego samego ziarna będzie generować ten sam wzór liczb za każdym razem.

Z dokumentów Java, jest to celowa funkcja przy określaniu wartości początkowej dla losowej klasy.

Jeśli dwie instancje losowe zostaną utworzone z tego samego ziarna, a dla każdego wykonywana jest ta sama sekwencja wywołań metod, generują one I zwraca identyczne ciągi liczb. Aby to zagwarantować właściwość, określone algorytmy są określone dla klasy Random. Implementacje Javy muszą wykorzystywać wszystkie algorytmy przedstawione tutaj dla class Random, for ze względu na absolutną przenośność kodu Java.

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

Dziwne jednak, można by pomyśleć, że istnieją ukryte problemy z bezpieczeństwem w przewidywalnych "losowych" liczb.

Chodzi o "ziarno". Te same nasiona dają ten sam wynik.

Oto niewielka poprawa dla Denis Tulskiy Odpowiedź . Skraca czas o połowę

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