How to generate all alphanumeric combinations of N characters

Question

For writing a general purpose decoder a a personal project, I am trying to generate all alphanumeric combinations of any given length.

I have something along these lines functioning, but i highly doubt it will generate all of them, as it seem biased towards letter combinations.

Code:

    {
        string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        List<string> combinations = new List<string>();


        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
           
            var random = new Random();



            for (int x = 0; x <= 999; x++)
            {

                combinations.Add(chars[random.Next(chars.Length)].ToString());
                for (int i = 0; i <= 8; i++)
                {
                    combinations[x]+= chars[random.Next(chars.Length)].ToString();



                }


            }
        }

        private void button2_Click(object sender, EventArgs e)
        {
            for (int x=0; x<99; x++)
            {
                Console.WriteLine(combinations[x]);

            }
        }
    }

Can anyone explain to me how to generate all of them of any given length? I'm thinking of nested for loops, with conditional statements. So if combinations[x] < given length, then a for loops executes. Will this work? Or do you know a better method?

Greetings

If you have 36 possible characters and a length of 10 (as in your code), that gives you 36^10 = 3,656,158,440,062,976 possible combinations. Even if you generated 1 million combinations per second, it would take a century to generate all of them. — Michael Liu, Aug 21 '23 at 17:57

André Luís de Andrade · Accepted Answer · 2023-08-22T18:07:48.667

Ok, this is a bit of a tough challenge. Glancing at it, it looks like your method works. That is, if you hit button1 enough times (aka more times than anyone will ever have the patience to), it will generate all possible combinations.

The reason why it seems biased towards letters, is because it is. There are 26 letters and only 10 digits, that makes any given character be 2.6 times more likely to be a letter than a digit.

The reason I say this is a tough challenge is the sheer amount of combinations, since it grows exponentially with the length of the string.

There are 36 characters

A string of length 1 has 36 ^ 1 = 36 possible combinations
A string of length 2 has 36 ^ 2 = 1296 possible combinations
At length 10 that's 3.656.158.440.062.976 possible combinations

You cannot hope to generate every possible combination for any string length, because at a mere 50 length that will be (assuming 1 byte per char) 1 byte * 50 * 36 ^ 50. That's a number with 77 digits, and it's how many bytes it'll take up. Take out 9 digits and you got a number of gigabytes with 68 digits, which I would imagine is slightly more than your computer's memory can handle

All of that said, I've come up with a way to do that. It's horribly inefficient as it copies lists and strings all over the place, but given the inefficiency of the problem itself, it should at least get you a starting point.

public static List<string> Generate(int stringLength) {
  return Generate(stringLength, new());
}

private static List<string> Generate(int stringLength, List<string> combinations) {
  const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

  if (stringLength is 1) {
    return ALPHABET.ToCharArray().Select(c => c.ToString()).ToList();
  }

  combinations = Generate(stringLength - 1, combinations);
  var newCombinations = new List<string>();

  foreach (var combination in combinations) {
    foreach (var character in ALPHABET) {
      newCombinations.Add($"{character}{combination}");
    }
  }

  return newCombinations;
}

Also I only mentioned storage, the time it would take to generate all of these combinations will also be ridiculously long. At a trillion combinations per second (which is VERY, VERY generous), it would take 2 octodecillion years to generate all 50 character combinations, which is probably slightly longer than your lifetime, and possibly the Universe's lifetime — André Luís de Andrade, Aug 21 '23 at 18:07
After thinking about it for a while I managed to write a piece of code that does solve your problem by using recursion to create all the combinations. Hope it helps — André Luís de Andrade, Aug 22 '23 at 18:09

How to generate all alphanumeric combinations of N characters

1 Answers1