题 为什么这段代码使用随机字符串打印“hello world”?


以下print语句将打印“hello world”。 谁能解释一下呢?

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

randomString() 看起来像这样:

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

1591
2018-03-03 04:38


起源


那么,那些特殊的种子恰好是完美的。随机不是真正的随机,它是伪随机的。 - Doorknob
正如其他人所说,它的作用是因为随机不是。对我来说,一个更有趣的问题是那个写下来的人,蛮力强迫它,或者是否有一种简单的方法来预测随机将为给定种子的下一个N值产生什么。蛮力很容易,现代硬件不应该花费太长时间,因此这是一种可行的方法。鉴于它是静态的,您甚至可以轻松地在网络上分发搜索。 - jmoreno
我想知道的目的 n 在 for (int n = 0; ; n++)。他们可以使用 for(;;) 要么 while(true) 代替! - Eng.Fouad
在一个真正随机的序列中,最终会出现每个可能的字符在高质量的伪随机序列中,可以合理地期望每个可能的长度字符串(log_s(N) - n)位(其中N是PRNG内部状态中的位数,n是一个小数字,为方便起见,选择8) )出现在循环中。这段代码从使用自由选择的硬编码起点(字符反引号的值)获得了一些帮助,它几乎得到了整个8位。 - dmckee
印刷“你好世界”的最奇怪方式的赢家 - osdamv


答案:


当一个实例 java.util.Random 用特定的种子参数构造(在这种情况下) -229985452 要么 -147909649),它遵循随机数生成算法 开始 有那个种子价值。

一切 Random 使用相同的种子构造将每次生成相同的数字模式。


846
2018-03-03 04:40



@Vulcan - javadoc说种子是48位。 docs.oracle.com/javase/7/docs/api/java/util/Random.html。此外,实际种子是32位值。 - Stephen C
随机数序列的每个元素取模27,并且每个元素中有6个元素 "hello\0" 和 "world\0"。如果你假设一个真正的随机发生器,获得你正在寻找的序列的概率是27 ^ 6(387,420,489)中的1 - 所以它相当令人印象深刻,但不是很令人兴奋! - Russell Borogove
@RussellBorogove:但是有了这些可能性,以及2 ^ 64种可能的种子,预计有476亿个种子值可以提供该序列。这只是找到一个问题。 - dan04
@ dan04 - 我不太愿意做出那个估计;取决于PRNG的实现,种子字的大小可能不等于状态的大小,并且序列路径可能不是均匀分布的。但仍然,赔率肯定是好的,如果你找不到一对,你可以尝试不同的套管("Hello"  "World"),或使用 122-k 代替 96+k, 要么... - Russell Borogove
@ThorbjørnRavnAndersen Javadoc 指定“为Random类指定特定算法。为了Java代码的绝对可移植性,Java实现必须使用此处显示的所有算法用于Random类。” - Vulcan


其他答案解释了原因,但这里是如何。

给出一个例子 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

1086
2018-03-03 04:55



迂腐, new Random(-229985452).nextInt(27) 总是返回8。 - immibis
@immibis为什么?我的意思是Random()应该每次返回随机数,而不是修复有序数字集? - roottraveller
@rootTraveller首先, new Random() 根本不会返回一个数字。 - immibis
@immibis晚了4年零一个月,但是为ya固定。 ; d - jpmc26


我会把它留在这里。谁有很多(CPU)的时间,随时可以试验:)另外,如果你已经掌握了一些fork-join-fu来使这个东西烧掉所有CPU内核(只是线程很无聊,对吗?),请分享你的代码。我将不胜感激。

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

输出:

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

263
2018-03-03 15:03



@一二三 nextInt(27) 意味着在范围内 [0, 26]。 - Eng.Fouad
@Vulcan大多数种子非常接近最大值,就像你选择1到1000之间的随机数一样,你最终选择的大多数种子将有三位数。当你想到它时,这并不奇怪:) - Thomas
@Vulcan事实上,如果你进行数学运算,你会发现它们与零的最大值接近(我认为种子在生成代码中被解释为无符号)。但是因为数字的数量只与实际值成对数增长,所以当数字真的没有时,数字看起来非常接近。 - Thomas
一个有趣且相关的规则是 本福德定律,在许多自然数据来源中,前导数字“1”和“2”出现得更频繁,原因类似:从9到10比10到20要小得多。在这种情况下,来自 0 至 int.max/10 比起来要少得多 int.max/10 至 int.max。 - FeepingCreature
@Marek:我不认为伪随机的神会赞成这种行为。 - Denis Tulskiy


这里的每个人都很好地解释了代码是如何工作的,并展示了如何构建自己的示例,但这里有一个信息理论答案,说明为什么我们可以合理地期望蛮力搜索最终会找到解决方案。

26个不同的小写字母组成了我们的字母表 Σ。为了允许生成不同长度的单词,我们进一步添加终止符号  产生扩展字母表 Σ' := Σ ∪ {⊥}

α 是一个符号,X是一个均匀分布的随机变量 Σ'。获得该符号的概率, P(X = α),及其信息内容, I(α),由下列人员给出:

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

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

一句话 ω ∈ Σ* 和它的 ⊥-终止对方 ω' := ω · ⊥ ∈ (Σ')*, 我们有

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

由于伪随机数发生器(PRNG)是用32位种子初始化的,我们可以期待大多数单词的长度达到

λ= floor [32 / log 2(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


248
2018-03-04 09:49



我的信息理论有点弱,但我喜欢这个证明。有人可以向我解释lambda线,显然我们将一个信息内容与另一个信息内容分开,但为什么这会给我们字长呢?正如我所说,我有点生气,所以道歉要求明显(N.B.是否与shannon限制有关 - 来自代码输出) - Mike H-R
@ MikeH-R lambda线是 I(⍵) 方程重新排列。I(⍵) 是32(位)和 |⍵| 原来是5(符号)。 - iceman


我写了一个快速程序来找到这些种子:

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

我现在在后台运行它,但它已经找到了足够的经典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);
        }
    }
}

在ideone上演示。

PS。 -727295876, -128911, -1611659, -235516779


65
2018-03-03 18:33



class R{ public static void main(String[] a) { System.out.println("-229985452, -147909649"); } 这项工作也是如此。 - djechlin


我对此很感兴趣,我在字典单词列表上运行了这个随机单词生成器。 范围: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 

31
2018-04-13 22:47



你做了我的一天男人:DI尝试了Long.Min / Max并搜索我的同事的名字,只找到彼得:(彼得4611686018451441623彼得24053719彼得-4611686018403334185彼得-9223372036830722089彼得-4611686017906248127彼得521139777彼得4611686018948527681彼得-9223372036333636031彼得 - 4611686017645756173 peter 781631731 peter 4611686019209019635 peter -9223372036073144077 peter -4611686017420317288 peter 1007070616 peter -9223372035847705192) - Marcel


事实上,大多数随机数发生器都是“伪随机数”。它们是线性同余发生器或LCG(http://en.wikipedia.org/wiki/Linear_congruential_generator

鉴于固定种子,LCG是可预测的。基本上,使用一个为您提供第一个字母的种子,然后编写一个继续生成下一个int(char)的应用程序,直到您点击目标字符串中的下一个字母并记下您必须调用LCG的次数。继续,直到你生成每一个字母。


26
2018-03-04 10:59



什么是非伪随机数发生器的一个例子 - chiliNUT
@chiliNUT这样的生成器是外部小工具。一些电子灯。或写得不好的读取0或1的位。你不能做随机数的纯数字发生器,数字算法不是随机的,它们绝对精确。 - Gangnus
@chiliNUT许多操作系统都在收集 熵。例如。在Linux中你可以使用 /dev/urandom 设备读取随机数据。然而,这是一种稀缺资源。因此,这种随机数据通常用于种子PRNG。 - Adrian W
@AdrianW维基百科说 urandom 仍然是伪随机的 en.wikipedia.org/wiki//dev/random - chiliNUT
是的,但它是加密安全的,这意味着人们不能使用从中创建的随机序列进行暴力攻击(比如找到“随机”序列“hello world”的种子) /dev/random。我上面引用的文章说 Linux内核通过键盘计时,鼠标移动和IDE计时生成熵,并通过特殊文件/ dev / random和/ dev / urandom使随机字符数据可用于其他操作系统进程。 这让我相信它是随机的。可能那不完全正确。但 /dev/random 至少 包含 一些熵。 - Adrian W


随机总是返回相同的序列。它用于改组数组和其他操作作为排列。

要获得不同的序列,必须在某个位置初始化序列,称为“种子”。

randomSting获得“随机”序列的i位置(seed = -229985452)中的随机数。然后使用 ASCII 在种子位置之后的序列中接下来的27个字符的代码,直到此值等于0.这将返回“hello”。对“世界”进行相同的操作。

我认为代码不适用于任何其他单词。编程的人非常了解随机序列。

这是非常棒的极客代码!


22
2018-03-03 04:54



我怀疑他是否“非常了解随机序列”。更可能的是,他只是尝试了数十亿种可能的种子,直到找到一种有效的种子。 - dan04
@ dan04真正的程序员不仅仅使用PRNG,他们会记住整个时期并根据需要枚举值。 - Thomas
“随机总是返回相同的序列” - 在Random之后put()或将其显示为代码。除此之外,这句话是错误的。 - Gangnus