Vraag Waarom wordt met deze code met willekeurige tekenreeksen "Hello World" afgedrukt?


De volgende printinstructie zou "Hello World" afdrukken. Kan iemand dit uitleggen?

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

En randomString() het lijkt hierop:

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

1588
2018-03-03 04:38


oorsprong


antwoorden:


Wanneer een instantie van java.util.Random is geconstrueerd met een specifieke seed-parameter (in dit geval -229985452 of -147909649), volgt het het algoritme voor het genereren van willekeurige getallen begin met die seed-waarde.

elk Random geconstrueerd met hetzelfde zaad, genereert telkens hetzelfde nummerpatroon.


844
2018-03-03 04:40



De andere antwoorden verklaren waarom, maar hier is hoe.

Gegeven een instantie van Random:

Random r = new Random(-229985452)

De eerste 6 nummers dat r.nextInt(27) genereert zijn:

8
5
12
12
15
0

en de eerste 6 nummers dat r.nextInt(27) genereert gegeven Random r = new Random(-147909649) zijn:

23
15
18
12
4
0

Voeg vervolgens die getallen toe aan de integer-weergave van het teken ` (wat 96 is):

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

1084
2018-03-03 04:55



Ik laat het hier gewoon achter. Degene die veel (CPU) tijd over heeft, is vrij om te experimenteren :) Ook als je wat fork-join-fu onder de knie hebt om dit ding alle CPU-kernen te laten verbranden (alleen threads zijn saai, toch?), Deel jouw code. Ik zou het enorm op prijs stellen.

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

Output:

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

262
2018-03-03 15:03



Iedereen hier heeft goed uitgelegd hoe de code werkt en laat zien hoe je je eigen voorbeelden kunt construeren, maar hier is een informatie-theoretisch antwoord dat laat zien waarom we redelijkerwijs kunnen verwachten dat er een oplossing bestaat die de zoektocht naar brute kracht uiteindelijk zal vinden.

De 26 verschillende kleine letters vormen ons alfabet Σ. Om het genereren van woorden van verschillende lengten mogelijk te maken, voegen we verder een terminatorsymbool toe  om een ​​uitgebreid alfabet op te leveren Σ' := Σ ∪ {⊥}.

Laat α een symbool zijn en X een uniform verdeelde willekeurige variabele over Σ'. De kans om dat symbool te verkrijgen, P(X = α)en de informatie-inhoud ervan, I(α), worden gegeven door:

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

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

Voor een woord ω ∈ Σ* en zijn ⊥-beëindigde tegenpartij ω' := ω · ⊥ ∈ (Σ')*, we hebben

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

Aangezien de Pseudorandom Number Generator (PRNG) is geïnitialiseerd met een 32-bits seed, kunnen we de meeste woorden van lengte verwachten tot

λ = verdieping [32 / log₂ (27)] - 1 = 5

om te worden gegenereerd door ten minste één zaadje. Zelfs als we zouden zoeken naar een woord met zes tekens, zouden we nog steeds ongeveer 41.06% van de tijd succesvol zijn. Niet te shabby.

Voor 7 letters kijken we dichter naar 1,52%, maar ik had me dat niet gerealiseerd voordat ik het probeerde:

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

Zie de output: http://ideone.com/JRGb3l


248
2018-03-04 09:49



Ik schreef een snel programma om deze zaden te vinden:

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

Ik heb het nu op de achtergrond, maar het heeft al genoeg woorden gevonden voor een klassieke 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);
        }
    }
}

(Demo op ideone.)

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


65
2018-03-03 18:33



Ik was hier geïntrigeerd door, ik leidde deze willekeurige woordgenerator op een woordenboekwoordenlijst. Bereik: Integer.MIN_VALUE tot Integer.MAX_VALUE

Ik kreeg 15131 hits.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

prints

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



De meeste willekeurige-nummergeneratoren zijn in feite "pseudo-willekeurig". Het zijn Lineaire Congruentiegeneratoren of LCG's (http://en.wikipedia.org/wiki/Linear_congruential_generator)

LCG's zijn redelijk voorspelbaar gezien een vast zaad. Gebruik in principe een zaadje dat je je eerste letter geeft, en schrijf vervolgens een app die de volgende int (char) blijft genereren tot je de volgende letter in je doelreeks raakt en noteer hoe vaak je de LCG hebt aangeroepen. Ga door totdat je elke letter hebt gegenereerd.


26
2018-03-04 10:59



Willekeurig retourneert altijd dezelfde reeks. Het wordt gebruikt voor herverdeling van arrays en andere bewerkingen als permutaties.

Om verschillende reeksen te krijgen, moet de reeks in een bepaalde positie worden geïnitialiseerd, genaamd "seed".

De randomSting krijgt het willekeurige getal in de i-positie (seed = -229985452) van de "willekeurige" reeks. Gebruikt vervolgens de ASCII code voor het volgende 27 tekens in de reeks na de zaadpositie totdat deze waarde gelijk is aan 0. Hiermee wordt de "hallo" geretourneerd. Dezelfde bewerking wordt gedaan voor "wereld".

Ik denk dat de code niet werkte voor andere woorden. De man die heeft geprogrammeerd, kent de willekeurige volgorde heel goed.

Het is een geweldige geek-code!


22
2018-03-03 04:54



Omdat multi-threading erg gemakkelijk is met Java, is hier een variant die zoekt naar een seed met alle beschikbare cores: 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();
    }
  }
}

22
2017-10-04 23:13