Dlaczego ten kod za pomocą losowych ciągów wypisuje „hello world”?

Poniższa instrukcja print wyświetli „hello world”. Czy ktoś mógłby to wyjaśnić?

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

I randomString()wygląda tak:

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

Gdy instancja java.util.Randomjest konstruowana z określonym parametrem początkowym (w tym przypadku -229985452lub -147909649), postępuje zgodnie z algorytmem generowania liczb losowych rozpoczynającym się od tej wartości początkowej .

Każde Randomzbudowane z tego samego materiału siewnego będzie generować ten sam wzór liczb za każdym razem.

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

Biorąc pod uwagę przykład Random:

Random r = new Random(-229985452)

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

8
5
12
12
15
0

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

23
15
18
12
4
0

Następnie po prostu dodaj te liczby do reprezentacji liczb całkowitych 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. Ktokolwiek ma dużo czasu (procesora) do stracenia, nie krępuj się eksperymentować :) Ponadto, jeśli opanowałeś rozwidlenie, aby spalić wszystkie rdzenie procesora (tylko wątki są nudne, prawda?), Udostępnij Twó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();
}

Wynik:

-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 słusznie oczekiwać rozwiązania, które w końcu znajdzie brutalne wyszukiwanie.

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

Niech αbędzie symbolem, a X równomiernie rozmieszczoną zmienną losową Σ'. Prawdopodobieństwo uzyskania tego symbolu P(X = α)oraz jego zawartości informacyjnej I(α)są określone przez:

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

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

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

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

Ponieważ Generator liczb pseudolosowych (PRNG) jest inicjowany za pomocą 32-bitowego materiału źródłowego, możemy spodziewać się większości słów o długości do

λ = piętro [32 / log₂ (27)] - 1 = 5

do wygenerowania przez co najmniej jedno ziarno. Nawet gdybyśmy szukali słowa składającego się z 6 znaków, nadal odnosilibyśmy sukces przez około 41,06% czasu. Nieźle.

W przypadku 7 liter przyglądamy się bliżej 1,52%, ale nie zdawałem sobie z tego sprawy, zanim spróbowałem:

#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 wynik: http://ideone.com/JRGb3l

Napisałem szybki program do znalezienia tych nasion:

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 teraz uruchomionego w tle, ale znalazłem już wystarczająco dużo słów na klasyczny 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.

Byłem tym zaintrygowany, uruchomiłem ten generator losowych słów na liście słów w słowniku. Zakres: Integer.MIN_VALUE do Integer.MAX_VALUE

Mam 15131 trafień.

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

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

Wydruki

the quick browny fox jumps over a lazy dog 

Większość generatorów liczb losowych jest w rzeczywistości „pseudolosowymi”. Są to liniowe generatory conruential lub LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCG są dość przewidywalne, biorąc pod uwagę ustalone nasiona. Zasadniczo użyj zarodka, który daje ci pierwszą literę, a następnie napisz aplikację, która generuje następne int (char), aż trafisz następną literę w docelowym ciągu i zapisz, ile razy trzeba było wywoływać LCG. Kontynuuj, aż wygenerujesz każdą literę.

Ponieważ wielowątkowość jest bardzo łatwa w Javie, oto wariant, który wyszukuje ziarno za pomocą 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();
    }
  }
}

Losowo zawsze zwraca tę samą sekwencję. Służy do tasowania tablic i innych operacji jako permutacji.

Aby uzyskać różne sekwencje, konieczne jest zainicjowanie sekwencji w pewnej pozycji, zwanej „seed”.

Funkcja randomSting otrzymuje liczbę losową w pozycji i (seed = -229985452) „losowej” sekwencji. Następnie używa kodu ASCII dla kolejnych 27 znaków w sekwencji po pozycji początkowej, aż wartość ta będzie równa 0. Zwróci to „hello”. Ta sama operacja jest wykonywana dla „świata”.

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

To bardzo świetny kod maniaka!

Głównym jest, że klasa losowa zbudowana z tego samego materiału siewnego będzie generować ten sam wzór liczb za każdym razem.

Ta metoda, wywodząca się z odpowiedzi Denisa Tulskiego , 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 :/");
}

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

Jeśli dwa wystąpienia Losowe zostaną utworzone z tym samym ziarnem i dla każdego zostanie utworzona ta sama sekwencja wywołań metod, wygenerują one i zwrócą identyczne ciągi liczb. W celu zagwarantowania tej właściwości określone algorytmy są określone dla klasy Losowo. Implementacje Java muszą używać wszystkich przedstawionych tutaj algorytmów dla klasy Random ze względu na absolutną przenośność kodu Java.

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

Dziwne, wydaje się, że istnieją domniemane problemy bezpieczeństwa związane z przewidywalnymi „losowymi” liczbami.

Chodzi o „nasiona”. Te same nasiona dają ten sam rezultat.

Oto niewielka poprawa odpowiedzi Denisa Tulskiego . 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 :/");
}

Chodzi o ziarno wejściowe . Te same nasiona dają te same wyniki przez cały czas. Nawet jeśli ponownie uruchomisz program, to samo wyjście.

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

}

Wynik

-755142161
-1073255141
-369383326
1592674620
-1524828502
------------
-755142161
-1073255141
-369383326
1592674620
-1524828502