下面的打印语句将打印“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();
}

当前回答

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

给定固定的种子,LCG是非常可预测的。基本上,使用给你第一个字母的种子,然后编写一个应用程序,继续生成下一个int(char),直到你命中目标字符串中的下一个字母,并记下你需要调用LCG的次数。继续,直到生成每个字母。

其他回答

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

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

设α是符号,X是∑′上均匀分布的随机变量。获得该符号P(X=α)及其信息内容I(α)的概率由下式给出:

P(X=α)=1/|∑'|=1/27I(α)=-log₂[P(X=α)]=-log₂(1/27)=对数₂(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

这都是关于输入种子的。相同的种子产生相同的结果时间。即使你一次又一次地重新运行你的程序,它的输出也是一样的。

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

Random始终返回相同的序列。它用于重排数组和其他排列操作。

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

randomSting在“随机”序列的i位置(种子=-22985452)获得随机数。然后将ASCII码用于种子位置之后的序列中的下一个27个字符,直到该值等于0。这将返回“hello”。同样的操作也适用于“世界”。

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

这是非常棒的极客代码!

我就把它留在这里。如果你掌握了一些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

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