Generating a recursive series of letters (like Excel column headers)

Question

Long story short I am trying to create some sort of chess library that would work potentially for chess boards of any size up to, maybe, int.MaxValue by int.MaxValue. Generating an infinite list of rank number is easy enough:

    static IEnumerable<int> GetRankNumbers()
    {
        for(int i = 1; ; i++)
            yield return i;
    }

But for generating file letters, I am currently doing this:

    static IEnumerable<string> GetFileLetters()
    {
        const string theLetters = "abcdefghjklmnopqrstuvwxyz"; // there is no 'i'.

        for(int i = 0; ; i++)
        {
            var factor = i / theLetters.Length;
            var index = i % theLetters.Length;

            var sb = new StringBuilder();
            sb.Append(theLetters[index]);

            for(int j = 0; j < factor; j++)
            {
                sb.Append(theLetters[index]);
            }

            yield return sb.ToString();
        }
    }

Which produces the following:

var x = GetFileLetters().Take(100);
foreach(var item in x) Write(item + " ");

Output:
a b c d e f g h j k l m n o p q r s t u v w x y z aa bb cc dd ee ff gg hh jj kk ll mm nn oo pp qq rr ss tt uu vv ww xx yy zz aaa bbb ccc ddd eee fff ggg hhh jjj kkk lll mmm nnn ooo ppp qqq rrr sss ttt uuu vvv www xxx yyy zzz aaaa bbbb cccc dddd eeee ffff gggg hhhh jjjj kkkk llll mmmm nnnn oooo pppp qqqq rrrr ssss tttt uuuu vvvv wwww xxxx yyyy zzzz

As you can see, for just a 100 items, it balloons quickly. How can I make it so it returns the results as a, b, c, ..., z, aa, ab, ac, ... , az, ba, bb, .. etc ?

Bonus question: how do I do this in F# as well?

PS. I found some similar questions here, here, and here, but none of them do it with IEnumerable, yield return, and a theoretically infinite set like I am trying to. The last one is rather cheating (Coming to think of it I don't really need more .. but I am doing this to learn).

Show your attempts to solve. Ask specific questions - translated almost one to one. — FoggyFinder, Jun 18 '16 at 18:21
You say "like excel column headers" and then you generate aa, bb, cc, etc. You should be generating aa, ab, ac, ad, ... az, ba, bb, bc, ... bz, ca, cb, cc, cd, ... shouldn't you? — Lasse V. Karlsen, Jun 18 '16 at 18:22
http://stackoverflow.com/questions/923771/quickest-way-to-convert-a-base-10-number-to-any-base-in-net — Janne Matikainen, Jun 18 '16 at 18:23
@FoggyFinder I'm stumped on even how I would begin to do this. I think the question is fairly specific: how can I use an Iterator within itself in C# — asibahi, Jun 18 '16 at 18:23
Check this [.NET Fiddle](https://dotnetfiddle.net/tPi34Z) I created, I *think* it should do what you want. — Lasse V. Karlsen, Jun 18 '16 at 18:33
@LasseV.Karlsen thanks !! Could you post this as answer please? — asibahi, Jun 18 '16 at 18:39
I thought about this variant: https://dotnetfiddle.net/MwWMfo — FoggyFinder, Jun 18 '16 at 18:40

score 6 · Answer 1 · answered Jun 18 '16 at 18:43

First, let's construct a function that will produce a sequence of n-character combinations. For n=1 (base case), it will produce just a sequence of single characters. For n=2 it will produce all combinations of 2 characters. And so on.

For a given n, how do we produce all combinations of n characters? First we prepend "a" to all combinations of n-1 characters, then we prepend "b" to all combinations of n-1 characters, and so on:

let rec seqOfNChars n = 
  seq {
    for c in ['a' .. 'z'] do
      for s in seqOfNChars (n-1) do
        yield sprints "%c%s" c s
  }

Then add the base case:

let rec seqOfNChars n = 
  seq {
    for c in ['a' .. 'z'] do
      if n <= 1 then
        yield string c
      else
        for s in seqOfNChars (n-1) do
          yield sprintf "%c%s" c s
  }

Now that we have this function, we can easily produce a sequence of all combinations of all lengths, starting with 1:

let allHeaders = Seq.initInfinite ((+) 1) |> Seq.collect seqOfNChars

score 2 · Accepted Answer · answered Jun 18 '16 at 18:44

One way would be to recursively create all column names with depth X and then sequentially just go one depth deeper each iteration.

Here's a basic solution that does just that in C#:

public static IEnumerable<string> GetColumns()
{
    int depth = 1;
    while (true)
    {
        foreach (var column in GetColumns(depth))
            yield return column;
        depth++;
    }
}

private static IEnumerable<string> GetColumns(int depth)
{
    string letters = "abcdefghijklmnopqrstuvwxyz";
    foreach (var c in letters)
        if (depth == 1)         
            yield return c.ToString();
        else
        {
            foreach (var sub in GetColumns(depth - 1))
                yield return c + sub;
        }
}

You can see this in this .NET Fiddle that you can play with.

Please note that I have not tested this extensively so you should check boundary cases to see that it does the right thing.

Also note that this will create a lot of string garbage. If you want to avoid that you should probably build the strings in a different manner.

Max · Answer 3 · 2016-06-19T14:31:50.267

1

No need for recursion to convert an integer to another base:

IEnumerable<string> GetFileLetters()
{
    const string theLetters = "abcdefghjklmnopqrstuvwxyz"; // there is no 'i'.

    for (int i = 1; ; i++)
    {
        var s = "";
        var c = i;

        while (c > 0)
        {
            var m = (c - 1) % theLetters.Length;
            s = theLetters[m] + s;
            c = (c - m) / theLetters.Length;
        }

        yield return s;
    }
}

Obviously can (should) be optimized with memoization and string builder but the concept remains.

edited Jun 19 '16 at 14:31

answered Jun 18 '16 at 18:51

Max

3,453
3
32
50

Won't this also generate things like `a a`? (ie. spaces inbetween) – Lasse V. Karlsen Jun 18 '16 at 18:57
yeah I tested it. It does that and some of the strings are empty at the beginning as well. when I removed the space from the `letters` string it jumped to `ba` after `z`. – asibahi Jun 18 '16 at 19:02

Generating a recursive series of letters (like Excel column headers)

3 Answers3