Почему этот код с использованием случайных строк печатает & ldquo; hello world & rdquo ;?

Речь идет о «семени». Те же семена дают тот же результат.

Принцип - случайный класс, построенный с одним и тем же начальным числом, будет каждый раз генерировать одну и ту же комбинацию чисел.

Меня это заинтриговало, я запустил этот генератор случайных слов в списке словарных слов. Диапазон: от Integer.MIN_VALUE до Integer.MAX_VALUE

Я получил 15131 хитов.

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

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

Печать

the quick browny fox jumps over a lazy dog 

Другие ответы объясняют почему, но вот как.

Учитывая случай Random:

Random r = new Random(-229985452)

Первые 6 чисел, которые генерирует r.nextInt(27), являются:

8
5
12
12
15
0

и первые 6 чисел, которые генерирует r.nextInt(27) даны Random r = new Random(-147909649):

23
15
18
12
4
0

Затем просто добавьте эти числа к целочисленному представлению символа ` (который равен 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

Большинство генераторов случайных чисел фактически являются «псевдослучайными». Это линейные конгруэнтные генераторы или LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCG вполне предсказуемы при фиксированном начальном числе. В основном, используйте начальное число, которое дает вам ваше первое письмо, затем напишите приложение, которое продолжает генерировать следующее целое число (символ), пока вы не нажмете следующую букву в вашей целевой строке и не запишите, сколько раз вам приходилось вызывать LCG. Продолжайте, пока вы не сгенерируете каждую букву.

Я написал быструю программу, чтобы найти эти семена:

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

У меня это работает в фоновом режиме, но уже найдено достаточно слов для классической панграммы:

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

( Демонстрация на идеоне. )

Пс. -727295876, -128911, -1611659, -235516779.

Полученный из ответа Дениса Тульского , этот метод создает семя.

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

Случайные всегда возвращают одну и ту же последовательность. Он используется для перестановки массивов и других операций в качестве перестановок.

Чтобы получить разные последовательности, необходимо инициализировать последовательность в некотором положении, называемом «семя».

RandomSting получает случайное число в позиции i (seed = -229985452) «случайной» последовательности. Затем использует код ASCII для следующих 27 символов в последовательности после начальной позиции, пока это значение не станет равным 0. Это вернет "привет". Та же операция сделана для «мира».

Я думаю, что код не работает ни для каких других слов. Парень, который запрограммировал это, очень хорошо знает случайную последовательность.

Это очень крутой выродок!

В документации по Java это преднамеренная особенность при указании начального значения для класса Random.

Если два экземпляра Random создаются с одним и тем же начальным числом, и для каждого выполняется одинаковая последовательность вызовов методов, они будут генерировать и возвращать идентичные последовательности чисел. Чтобы гарантировать это свойство, для класса Random указаны конкретные алгоритмы. Реализации Java должны использовать все алгоритмы, показанные здесь для класса Random, ради абсолютной переносимости кода Java.

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

Как ни странно, вы бы думаю, что существуют неявные проблемы безопасности, связанные с предсказуемыми «случайными» числами.

Все здесь проделали большую работу, объяснив, как работает код, и продемонстрировали, как вы можете построить свои собственные примеры, но вот информационный теоретический ответ, показывающий, почему мы можем разумно ожидать, что существует решение, которое в конечном итоге найдет поиск методом перебора.

26 различных строчных букв образуют наш алфавит Σ. Чтобы позволить генерировать слова различной длины, мы дополнительно добавляем символ-терминатор ⊥, чтобы получить расширенный алфавит Σ' := Σ ∪ {⊥}.

Пусть α будет символом, а X - равномерно распределенной случайной величиной по Σ'. Вероятность получения этого символа P(X = α) и его информационное содержание I(α) определяются как:

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

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

Для слова ω ∈ Σ* и его ⊥- прекращено аналог ω' := ω · ⊥ ∈ (Σ')*, мы имеем

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

Поскольку генератор псевдослучайных чисел (PRNG) инициализируется с помощью 32-разрядного начального числа, мы можем ожидать, что большинство слов длина до

λ = пол [32 / log₂ (27)] - 1 = 5

для формирования по крайней мере одним начальным числом. Даже если бы мы искали слово из 6 символов, мы все равно добились бы успеха в 41,06% случаев. Не слишком потертый.

Для 7 букв мы смотрим ближе к 1,52%, но я не осознавал этого, прежде чем дать ему попробовать:

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

См. Вывод: http: // ideone .com / JRGb3l [+1126]

Это - все о входе семя . То же семя дает те же результаты все время. Даже Вы повторно выполняете свою программу снова и снова, это - тот же вывод.

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

}

Вывод

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