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.