Lazily generating ordered enumerable of all positive longs that only use the numerals `0` & `9`

Question

When I was answering this question - An algorithm for a number divisible to n - I proposed a solution that would generate an ordered enumerable of all positive longs that only use the numerals 0 & 9.

However I really wasn't happy with the two options I put forward. The first was not lazy and basically generated before returning the first value.

The second was closer to the mark, but the logic was rather complicated and it contained a lot of "magic" numbers

I'm interested in seeing if anyone can put forward a fast lazily generated solution for me preferably using the signature Func<IEnumerable<long>> generate = ...; or otherwise IEnumerable<long> Generate() { ... }.

My first option was:

Func<IEnumerable<long>> generateA = () =>
{
    Func<long, IEnumerable<long>> extend =
        x => new [] { x * 10, x * 10 + 9 };

    Func<long, IEnumerable<long>> generate2 = null;
    generate2 = x =>
        x <= 0L
        ? Enumerable.Empty<long>() 
        : new [] { x }
            .Concat(
                extend(x)
                    .SelectMany(y => generate2(y)))
            .OrderBy(z => z);

    return generate2(9L);
};

The second was:

Func<IEnumerable<long>> generateB = () =>
{
    var powers =
        Enumerable
            .Range(0, 18)
            .Aggregate(
                new List<long>() { 1L },
                (a, _) => { a.Add(a.Last() * 10); return a; })
            .ToArray();

    return Enumerable
        .Range(1, 393215) //largest expressable value using `0` & `9` only.
        .Select(i => new BitArray(new [] { i })
            .Cast<bool>()
            .Take(19) //largest expressable value using `0` & `9` only.
            .Select((x, n2) => (x ? 9L : 0L) * powers[n2])
            .Sum());
};

Both methods return 393,215 values starting with 9 and ending with 9,099,999,999,999,999,999.

Any ideas to make a method that is lazy and simple?

Answer 1

I think it is easier to write understandable, lazy methods using yield return which isn't available in lambdas. Trying to do this only with LINQ makes it harder understand.

public class Program
{
    public static void Main(string[] args)
    {
        var items = Generate();

        var first = items.Take(8);
        var count = items.Count();
        var last = items.Skip(count - 4);
        Console.WriteLine("First items: {0}", string.Join(", ", first));
        Console.WriteLine("Last items: {0}", string.Join(", ", last));
        Console.WriteLine("Count: {0}", count);
    }

    private static IEnumerable<long> Generate()
    {
        return GenerateAll().TakeWhile(i => i >= 0);            
    }

    // generates an infinite sequence using GenerateNext
    private static IEnumerable<long> GenerateAll()
    {
        IEnumerable<long> items = new[] { 9L };

        while(true)
        {
            foreach(var item in items)
            {
                yield return item;
            }
            items = GenerateNext(items);
        }
    }

    // generates the next items in the sequence.
    private static IEnumerable<long> GenerateNext(IEnumerable<long> xs)
    {
        foreach(var x in xs)
        {
            long x2 = 10 * x;
            yield return x2;
            yield return x2 + 9;
        }            
    }
}

Output:

First items: 9, 90, 99, 900, 909, 990, 999, 9000
Last items: 9099999999999999900, 9099999999999999909, 9099999999999999990, 9099999999999999999
Count: 393215

Answer 2

Just for the record, my final answer was inspired by "Mike Z" - whom I'll give the answer to - and it was:

Func<IEnumerable<long>> generate = () =>
{
    Func<long, IEnumerable<long>> extend =
        x => new [] { x * 10, x * 10 + 9 };

    Func<IEnumerable<long>, IEnumerable<long>> generate2 = null;
    generate2 = ns =>
    {
        var clean = ns.Where(n => n > 0).ToArray();
        return clean.Any()
            ? clean.Concat(generate2(clean.SelectMany(extend)))
            : Enumerable.Empty<long>();
    };

    return generate2(new[] { 9L, });
};

This turns out to be lazy, in order, and very fast.