algorithm for generating a random numeric string, 10,000 chars in length?

Can be in any language or even ps开发者_JS百科eudocode. I was asked this in an interview question, and was curious what you guys can come up with.

---

I think this is a trick question - the obvious answer of generating digits using a standard library routine is almost certainly flawed, if you want to generate every possible 10000 digit number with equal probability...

If an algorithmic random number generator maintains n bits of state, then clearly it can generate at most 2ⁿ possible different output sequences, because there are only 2ⁿ different initial configurations.

2³³²¹⁹ < 10¹⁰⁰⁰⁰ < 2³³²²⁰, so if your algorithm uses less than 33220 bits of internal state, it cannot possibly generate some of the 10¹⁰⁰⁰⁰ possible 10000-digit (decimal) numbers.

Typical standard library random number generators won't use anything like this much internal state. Even the Mersenne Twister (the most frequently mentioned generator with a large state that I'm aware of) only keeps 624 32-bit words (= 19968 bits) of state.

---

Just one of many ways. You can pass in any string of the alphabet of characters you want to use:

public class RandomUtils
{
    private static readonly Random random = new Random((int)DateTime.Now.Ticks);

    public static string GenerateRandomDigitString(int length)
    {
        const string digits = "1234567890";

        return GenerateRandomString(length, digits);
    }

    public static string GenerateRandomAlphaString(int length)
    {
        const string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

        return GenerateRandomString(length, alpha);
    }


    public static string GenerateRandomString(int length, string alphabet)
    {
        int maxlen = alphabet.Length;

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < length; i++)
        {
            sb.Append(alphabet[random.Next(0, maxlen)]);
        }

        return sb.ToString();
    }
}

---

Without additional requirements, this will work:

StringBuilder randomStr = new StringBuilder(10000);
Random rnd = new Random();
for(int i = 0; i<10000;i++)
{
  char randomChar = rnd.AsChar();
  randomStr[i] = randomChar;
}

This will result in unprintable characters and other unpleasentness. Using an ASCII encoder you can get letters, numbers and punctutaiton by sticking to the range 32 - 126. Or creating a random number between 0 and 94 and adding 32. Not sure which aspect they were looking for in the question.

BTW, No I did not know the visible range off the top of my head, I looked it up on wikipedia.

---

Generate a number in the range 0..9. Convert it to a digit. Stuff that into a string. Repeat 10000 times.

---

I always like saying Computer Random Numbers are always only pseudo-random. Anyway, your favourite language will invariably have a random library. Next what is a numeric string ? 0-9 valued for each character ? Well let's start with that assumption. So we can generate bytes between to Ascii codes of 0-9 with offset (48) and (int) random*10 (since random generators typically return floats). Then place these all in a char buffer 10000 long and convert to string.

---

Return a string containing 10,000 1s -- that's just as random as any other digit string of the same length.

---

I think the real question was to determine what the interviewer actually wanted. For example, random in what sense? Uncompressable? Random over multiple runs of the same algorithm? Etc.

---

You can start with a list of seed digits:

seeds = [4,9,3,1,2,5,5,4,4,8,4,3] # This should be relatively large

Then, use a counter to keep track of which digit was last used. This would be system-wide and shouldn't reset with the system:

def next_digit():
    counter = 0
    while True:
        yield counter
        counter += 1
pos_it = next_digit()
rand_it = next_digit()

Next, use an algorithm that uses modulus to determine the "next number":

def random_digit():
    position = pos_it.next() % len(seeds)
    digit = seeds[position] * rand_it.next()
    return digit % 10

Last, generate 10,000 of those digits.

output = ""
for i in range(10000):
    output = "%s%s" % (output, random_digit())

I believe that an ideal answer would use more prime numbers, but this should be pretty sufficient.