Pourquoi ce code utilisant des chaînes aléatoires imprime-t-il «Bonjour tout le monde»?

Lorsqu’une instance de java.util.Random est construite avec un paramètre d’amorçage spécifique (dans ce cas, -229985452 ou -147909649 ), elle suit l’algorithme de génération de nombres aléatoires commençant par cette valeur de départ.

Chaque Random construit avec la même graine générera le même modèle de nombres à chaque fois.

Les autres réponses expliquent pourquoi, mais voici comment.

Étant donné une instance de Random :

 Random r = new Random(-229985452) 

Les 6 premiers nombres r.nextInt(27) par r.nextInt(27) sont:

 8 5 12 12 15 0 

et les 6 premiers nombres que r.nextInt(27) génère avec Random r = new Random(-147909649) sont:

 23 15 18 12 4 0 

Ajoutez simplement ces nombres à la représentation entière du caractère ` (qui est 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 

Je vais juste le laisser ici. Si vous avez beaucoup de temps (CPU) à dépenser, n’hésitez pas à faire des essais 🙂 En outre, si vous avez maîsortingsé fork-join-fu pour que cette opération grave tous les cœurs du processeur (juste les threads sont ennuyeux, non?), Partagez votre code. Je l’apprécierais beaucoup.

 public static void main(Ssortingng[] 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(Ssortingng goal) { long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE); System.out.println(seed[0]); System.out.println(randomSsortingng(seed[0], (char) seed[1])); } public static long[] generateSeed(Ssortingng 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(); } 

Sortie:

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

Tout le monde ici a fait un excellent travail en expliquant comment le code fonctionne et en montrant comment vous pouvez construire vos propres exemples, mais voici une réponse théorique expliquant pourquoi nous pouvons raisonnablement attendre une solution que la recherche par force brute finira par trouver.

Les 26 lettres minuscules différentes forment notre alphabet Σ . Pour permettre la génération de mots de différentes longueurs, nous ajoutons un symbole de terminaison ⊥ pour obtenir un alphabet étendu Σ' := Σ ∪ {⊥} .

Soit α un symbole et X une variable aléatoire uniformément dissortingbuée sur Σ' . La probabilité d’obtenir ce symbole, P(X = α) , et son contenu d’information, I(α) , sont donnés par:

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

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

Pour un mot ω ∈ Σ* et son homologue ⊥- terminé ω' := ω · ⊥ ∈ (Σ')* , nous avons

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

Puisque le générateur de nombres pseudo-aléatoires (PRNG) est initialisé avec une graine de 32 bits, on peut s’attendre à ce que la plupart des mots de longueur atteignent

λ = sol [32 / log₂ (27)] – 1 = 5

être généré par au moins une graine. Même si nous devions chercher un mot de 6 caractères, nous réussirions quand même environ 41,06% du temps. Pas trop mal.

Pour 7 lettres, nous nous rapprochons de 1,52%, mais je ne l’avais pas compris avant d’essayer:

 #include  #include  int main() { std::mt19937 rng(631647094); std::uniform_int_dissortingbution dist('a', 'z' + 1); char alpha; while ((alpha = dist(rng)) != 'z' + 1) { std::cout << alpha; } } 

Voir la sortie: http://ideone.com/JRGb3l

J’ai écrit un programme rapide pour trouver ces graines:

 import java.lang.*; import java.util.*; import java.io.*; public class RandomWords { public static void main (Ssortingng[] args) { Set wordSet = new HashSet(); Ssortingng 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 wordSet, Ssortingng fileName) { try { BufferedReader reader = new BufferedReader(new FileReader(fileName)); Ssortingng line; while ((line = reader.readLine()) != null) { line = line.sortingm().toLowerCase(); if (isLowerAlpha(line)) wordSet.add(line); } } catch (IOException e) { System.err.println("Error reading from " + fileName + ": " + e); } } private static boolean isLowerAlpha (Ssortingng 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 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); } } } } } 

Je l'ai en cours d'exécution en arrière-plan maintenant, mais il a déjà trouvé suffisamment de mots pour un pangram classique:

 import java.lang.*; import java.util.*; public class RandomWordsTest { public static void main (Ssortingng[] 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); } } } 

( Démo sur ideone. )

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

J’ai été insortinggué par cela, j’ai couru ce générateur de mots aléatoires sur une liste de mots du dictionnaire. Plage: Integer.MIN_VALUE à Integer.MAX_VALUE

J’ai 15131 visites.

 int[] arrInt = {-2146926310, -1885533740, -274140519, -2145247212, -1845077092, -2143584283, -2147483454, -2138225126, -2147375969}; for(int seed : arrInt){ System.out.print(randomSsortingng(seed) + " "); } 

Des tirages

 the quick browny fox jumps over a lazy dog 

La plupart des générateurs de nombres aléatoires sont en fait “pseudo-aléatoires”. Ce sont des générateurs linéaires, ou LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Les LCG sont assez prévisibles étant donné une graine fixe. Fondamentalement, utilisez une graine qui vous donne votre première lettre, puis écrivez une application qui continue à générer le prochain int (char) jusqu’à ce que vous ayez tapé la lettre suivante dans votre chaîne cible et notez combien de fois vous avez dû appeler le LCG. Continuez jusqu’à ce que vous ayez généré chaque lettre.

Random retourne toujours la même séquence. Il est utilisé pour mélanger les tableaux et autres opérations sous forme de permutations.

Pour obtenir des séquences différentes, il faut initialiser la séquence dans une certaine position, appelée “graine”.

Le randomSting obtient le nombre aléatoire dans la position i (graine = -229985452) de la séquence “aléatoire”. Ensuite, utilise le code ASCII pour les 27 caractères suivants dans la séquence après la position initiale jusqu’à ce que cette valeur soit égale à 0. Cela renvoie le “bonjour”. La même opération est effectuée pour “le monde”.

Je pense que le code n’a pas fonctionné pour d’autres mots. Le gars qui a programmé qui connaît très bien la séquence aléatoire.

C’est du très bon code geek!

Comme le multi-threading est très facile avec Java, voici une variante qui recherche une graine en utilisant tous les cœurs disponibles: 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 { private final char[] goal; private final long start, step; public SearchTask(final Ssortingng 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 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(); } } } 

Dérivée de la réponse de Denis Tulskiy , cette méthode génère la graine.

 public static long generateSeed(Ssortingng 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 :/"); } 

Le principal est la classe aléatoire construite avec la même graine générera le même modèle de nombres à chaque fois.

À partir des documents Java, il s’agit d’une fonctionnalité intentionnelle lors de la spécification d’une valeur de départ pour la classe aléatoire.

Si deux instances de Random sont créées avec la même graine et que la même séquence d’appels de méthode est faite pour chacune, elles généreront et renverront des séquences de nombres identiques. Afin de garantir cette propriété, des algorithmes particuliers sont spécifiés pour la classe Random. Les implémentations Java doivent utiliser tous les algorithmes présentés ici pour la classe Random, dans un souci de portabilité absolue du code Java.

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

Bizarrement, vous croyez qu’il ya des problèmes de sécurité implicites à avoir des nombres «aléatoires» prévisibles.

Il s’agit de “graine”. Les mêmes graines donnent le même résultat.

Voici une petite amélioration pour Denis Tulskiy. Il coupe le temps de moitié

 public static long[] generateSeed(Ssortingng 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 :/"); }