这段使用随机字符串的代码为什么会打印出“hello world”？

Question

以下打印语句将会输出 "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();
}

- 0x56794E

---

好的，那些特定的种子恰好完美地契合了。随机并非真正的随机，而是伪随机。 - tckmn

就像其他人所说的那样，它有效是因为随机数并不是真正随机的。对我而言，更有趣的问题是编写该程序的人是否采用暴力破解方式，或者是否有一种简单的方法来预测给定种子的下N个值将生成什么随机数。暴力破解很容易，并且使用现代硬件不应该花费太长时间，因此这确实是一种可行的方法。考虑到它是静态的，你甚至可以轻松地将搜索分布到网络中。 - jmoreno

我想知道 for (int n = 0; ; n++) 中的 n 的目的是什么。他们可以使用 for(;;) 或 while(true) 代替！ - Eng.Fouad

在一个真正的随机序列中，每个可能的字符串最终都会出现。在高质量的伪随机序列中，可以合理地期望长度为(log_s(N) - n)比特的每个可能字符串出现在循环中（其中N是PRNG内部状态中的比特数，n是一个小数字，我们选择8只是为了方便）。该代码通过使用一个自由选择的硬编码起始点（字符“ `”的值）来获得一些帮助，这几乎能够恢复整个8位。 - dmckee --- ex-moderator kitten

如果我要重构这个代码，除了重构花括号之外，我只会将方法名称更改为更具描述性的名称：“fixedAndNotSoRandomString”或其他类似的名称... - MC Emperor

Answer 1

其他答案已经解释了为什么，但是这里讲一下如何实现。

给定一个 Random 实例：

Random r = new Random(-229985452)

< p > r.nextInt(27) 生成的前6个数字是：

8
5
12
12
15
0

如果给定 Random r = new Random（-147909649），那么r.nextInt（27）生成的前6个数字是：

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

- Eng.Fouad

---

严格地说，new Random(-229985452).nextInt(27) 总是返回 8。 - user253751

@immibis 为什么？我的意思是 Random() 应该每次返回一个随机数，而不是一个固定的有序数字集合。 - roottraveller

首先，“new Random()”并不返回一个数字。 - user253751

@roottraveller，“随机”是一种确定性伪随机数生成器。如果您使用固定的种子进行初始化，它将产生一系列固定的数字。 - plugwash

这些种子是如何计算的？一定有某种逻辑...还是只是 brute force（暴力破解）呢？ - Sohit Gore

@SohitGore 鉴于Java的默认“Random”不具备加密安全性（我相信它是Mersenne Twister，但请勿引用我），因此可能可以从“我想要这些数字”逆推出“我将使用这个种子”。我曾经用标准的C线性同余生成器做过类似的事情。 - anon

Answer 2

当使用特定的种子参数（在本例中为-229985452或-147909649）构造java.util.Random的实例时，它将遵循从该种子值开始的随机数生成算法。

每个使用相同种子的Random实例每次都会生成相同的数字模式。

- FThompson

---

@Vulcan - javadoc上写道种子是48位。http://docs.oracle.com/javase/7/docs/api/java/util/Random.html。此外，实际的种子值是32位。 - Stephen C

随机数序列中的每个元素都取模27，每个"hello\0"和"world\0"有6个元素。假设你使用的是真正的随机生成器，那么获得你想要的序列的概率将是1/27^6（387,420,489）-- 所以这相当令人印象深刻但并不完全让人惊叹！ - Russell Borogove

@RussellBorogove说：“但是考虑到这些概率和2^64种可能的种子，预计有476亿个种子值会得出该序列。只是需要找到其中一个。” - dan04

@dan04 -- 我并不想给出具体的估计；因为PRNG实现的方式不同，种子大小可能与状态大小不相等，序列路径也可能不是均匀分布的。但是，机会肯定是很好的，如果您找不到一对，可以尝试使用不同的大小写（“Hello” “World”），或者使用122-k而不是96 + k，或者... - Russell Borogove

Javadoc指定了“为Random类指定了特定的算法。Java实现必须使用此处显示的所有算法，以确保Java代码的绝对可移植性。” - FThompson

Answer 3

我只是把它留在这里。有很多（CPU）时间可以浪费的人，随意尝试 :) 另外，如果你掌握了一些分叉-加入-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

- Denis Tulskiy

---

@OneTwoThree的nextInt(27)表示在区间[0, 26]内随机生成一个整数。 - Eng.Fouad

大多数种子都非常接近最大值，就像在1到1000之间随机选择数字一样，你最终选择的大多数数字都将有三个数字。当你想一想时，这并不令人惊讶 :) - Thomas

实际上，如果你算一下，你会发现它们距离最大值和零的距离几乎一样（我猜在生成代码中种子被解释为无符号数）。但由于数字的位数只随着实际值的对数增长，所以当实际差距很大时，数字看起来非常接近。 - Thomas

好的。为了获得额外的奖励分数，您是否能找到一个种子，用它初始化一个随机数生成器，该生成器将产生四个种子，以初始化最终的随机数生成器？ - Marek

@Marek：我认为伪随机数的神不会赞同这种行为。 - Denis Tulskiy

Answer 4

每个人都很好地解释了代码的工作原理并展示了如何构建自己的示例，但这里提供一个信息理论答案，显示为什么我们可以合理地期望存在一个解决方案，而暴力搜索最终将找到它。

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位种子进行初始化，我们可以预期大多数长度不超过

λ = floor[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

- xDD

Answer 5

我写了一个快速程序来寻找这些种子：

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

(在ideone上的演示)

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

- Ilmari Karonen

Answer 6

我对此很感兴趣，我在一个词典词汇列表上运行了这个随机单词生成器。 范围：整数最小值到整数最大值

我得到了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 

- Puru--

---

你让我感到非常开心 :D 我使用了 Long.Min/Max 并搜索了我的同事的名字，但只找到了彼得 :(彼得 4611686018451441623 彼得 24053719 彼得 -4611686018403334185 彼得 -9223372036830722089 彼得 -4611686017906248127 彼得 521139777 彼得 4611686018948527681 彼得 -9223372036333636031 彼得 -4611686017645756173 彼得 781631731 彼得 4611686019209019635 彼得 -9223372036073144077 彼得 -4611686017420317288 彼得 1007070616 彼得 -9223372035847705192 - Marcel

Answer 7

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

在固定种子的情况下，LCG是非常可预测的。基本上，使用一个种子来给你第一个字母，然后编写一个应用程序来继续生成下一个int（char），直到你碰到目标字符串中的下一个字母，并记录你必须调用LCG的次数。继续这个过程，直到你生成了每一个字母。

- Sinclair Schuller

Answer 8

由于Java非常容易实现多线程，以下是一种使用所有可用核心搜索种子的变体：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();
    }
  }
}

- TwoThe

---

对于像我这样的 Java 初学者，你需要在输出数字后缀上 L 并将参数类型更改为 long，即 randomString(long i) 以便进行实验。 :) - 林果皞

Answer 9

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

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

randomSting获取“random”序列中i位置（seed = -229985452）的随机数。然后使用种子位置之后的下一个27个字符的ASCII代码，直到这些值等于0。这返回“hello”。同样的操作也适用于“world”。

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

这是非常棒的极客代码！

- Arnaldo Ignacio Gaspar Véjar

---

我怀疑他“非常熟悉随机序列”。更可能的是，他只是尝试了数十亿个可能的种子，直到找到一个可行的。 - dan04

真正的程序员不仅使用伪随机数生成器，他们会牢记整个周期并根据需要枚举数值。 - Thomas

"Random总是返回相同的序列" - 在Random后面加上()或将其显示为代码。否则，该句是错误的。 - Gangnus

Answer 10

使用相同的种子构建的随机类（Random Class）每次生成的数字模式都是相同的。

- tomj0101