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

小开

最佳答案

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

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

小开

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

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

随机Sting在“随机”序列的i位置（种子=-229985452）获取随机数。然后对种子位置之后的序列中的下一个27个字符使用ASCII码代码，直到该值等于0。这将返回“hello”。对“world”执行相同的操作。

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

这是非常棒的极客代码！

小开

其他答案解释了为什么，但这是如何。

给定一个Random的实例：

Random r = new Random(-229985452)

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

851212150

给定Random r = new Random(-147909649)，r.nextInt(27)生成的前6个数字是：

2315181240

然后只需将这些数字添加到字符`（即96）的整数表示形式：

8  + 96 = 104 --> h5  + 96 = 101 --> e12 + 96 = 108 --> l12 + 96 = 108 --> l15 + 96 = 111 --> o
23 + 96 = 119 --> w15 + 96 = 111 --> o18 + 96 = 114 --> r12 + 96 = 108 --> l4  + 96 = 100 --> d

小开

另外，如果你已经掌握了一些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();}

输出：

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

小开

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

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

小开

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

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

设α是一个符号，X是Σ'上的均匀分布随机变量。获得该符号P(X = α)及其信息内容I(α)的概率由以下公式给出：

P（X = α) = 1/|Σ'| = 1/27
(α) = -log 2[P（X = α)] = -log 2（1/27）=log 2（27）

对于一个词ω ∈ Σ*和它的⊥-结尾的对应物ω' := ω · ⊥ ∈ (Σ')*，我们有

我(ω) := 我(ω') = |ω'| * log 2（27) = (|ω| + 1）*log 2（27）

由于伪随机数生成器（PRNG）是用32位种子初始化的，我们可以预期大多数长度为

λ=楼层[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

小开

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

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

小开

从Java文档中，这是为Random类指定种子值时的一个有意特性。

如果使用相同的种子创建了两个Random实例，并且对每个方法调用进行相同的序列，它们将生成和返回相同的数字序列。为了保证这一点属性，为类Random指定特定算法。Java实现必须使用此处显示的所有算法Class Random，为了Java代码的绝对可移植性。

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

奇怪的是，你会认为拥有可预测的“随机”数字存在隐含的安全问题。

小开

从DenisTulskiy的答案派生，此方法生成种子。

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

小开

主要是使用相同种子构建的随机类每次都会生成相同的数字模式。

小开

它是关于“种子”的。同样的种子会产生同样的结果。

小开

由于多线程使用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;}
@Overridepublic 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() {
@Overridepublic Thread newThread(Runnable r) {final Thread result = new Thread(r);result.setPriority(Thread.MIN_PRIORITY); // make sure we do not block more important tasksresult.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();}}}

小开

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

小开

这是Denis Tulskiy回答的一个小改进。它将时间缩短了一半

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

小开

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

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-3693833261592674620-1524828502-------------755142161-1073255141-3693833261592674620-1524828502