# Counting without zeroes

Below is a python script that generates the sequence ['a', 'b' .. 'z', 'aa', 'ab' .. 'az', 'ba', 'bb' .. 'zz', 'aaa', 'aab', ..]

This is essentially counting in base 27, replacing every digit with the n-th letter of the alphabet, but skipping any number that would have a '0'.

import string

def gen_labels():
i = 0
n = len(string.ascii_lowercase) + 1
while True:
i += 1
j = i
result = ''
while True:
c = j % n
if not c:
break
result = string.ascii_lowercase[c-1] + result
if j < n:
break
j = j // n
if c:
yield result

print(list(zip(gen_labels(), range(1000))))


However, the code seems overly long to me for generating such a straightforward series and it's doing a lot of work to break down values that would have a '0' in them in base 27.

What is a more efficient way of generating the exact same (infinite) series?

Note that I'm not worried that much about speed, but mainly about the brevity / simplicity of the algorithm - it seems overly complicated, but I don't really see my way to an efficient realisation.

• What is one of the numbers/letter combinations being skipped? – Graipher Nov 19 '19 at 8:38
• @Graipher he probably meant to say that no letter maps to number zero. – slepic Nov 19 '19 at 11:15
• @Barmar, actually no. Imagine an alphabet with only [a, b]. The series would be [a, b, aa, ab, ba, bb, aaa, etc.] - turn that into numbers and you get [0, 1, 00, 01, etc.] so it's not like counting in base 26, with that mapping. Instead, if you count in base 27 [0, 1, 2 .. p, 10, 11, 12, ..] and leave out the numbers containing 0, you get [1, 2 .. p, 11, 12, ..] and then map using 1 => a etc., you get the correct series. That's the whole issue, I just feel there may be a more efficient modelling of the same problem. – Grismar Nov 20 '19 at 2:53
• Is this bijective base-26, as used in many spreadsheets ? – David Cary Nov 22 '19 at 2:53
• You're right @DavidCary, thanks for putting a name to it - I wasn't aware. – Grismar Nov 22 '19 at 22:26

Well, what you want is just a product of the alphabet, with increasing numbers of elements. You can use itertools.product for this:

from itertools import product, count
from string import ascii_lowercase

def generate_labels():
"""Yields labels of the following form:
a, b, ..., z, aa, ab, ..., zz, aaa, aab, ..., zzz, ...
"""
for n in count(start=1):
yield from map("".join, product(*[ascii_lowercase]*n))


Here is what it outputs:

from itertools import islice

print(list(islice(generate_labels(), 1000)))
# ['a', 'b', ..., 'z', 'aa', 'ab', ..., 'az', 'ba', 'bb', ..., 'bz', ..., 'za', ..., 'zz', 'aaa', 'aab', ..., 'all']


This has the slight disadvantage that the list being passed to product gets larger every iteration. But already with $$\n=5\$$ you can generate $$\\sum_{k=1}^n 26^k = 12,356,630\$$ labels, and the list is only about sys.getsizeof([ascii_lowercase]*5) + sys.getsizeof(ascii_lowercase) * 5 = 479 bytes large, so in practice this should not be a problem.

I also made the name a bit longer (and clearer IMO) and added a docstring to briefly describe what the function is doing.

• You're right, it is just a full product with increasing length - exactly the fresh look at the problem I was after, thanks. – Grismar Nov 20 '19 at 3:43

The question is basically to continuously find the next lexicographically smallest string starting from 'a'

Here's the code I created to solve with recursion:

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

ALPS = 'abcdefghijklmnopqrstuvwxyz'

def parsed_string(l):
return ''.join(ALPS[i] for i in l)

def solve(string=None, i=0):
"""
Prints the next lexicographically smallest string infinitely:
a, b, ..., z, aa, ab, ..., zz, aaa, ..., zzz, ...
"""

# Entering a list as default parameter should be avoided in python
if string is None:
string = [0]

# Base case
if i == len(string):
print(parsed_string(string))
return

# Generate values if the current element is the alphabet
while string[i] < 26:
solve(string, i + 1)
string[i] += 1

# If the current index is the first element and it has reached 'z'
if i == 0:
string = [0] * (len(string) + 1)
solve(string)

else:
string[i] = 0

solve()


EDIT 1:

• This might cause MemoryError or RecursionError if the code is run for too long
• You can yield the value or append it to a list if you wish. The code was to provide a basic idea of how to solve the problem

Hope this helps!

• It's not wrong, but you're right - the recursion is risky, especially when you change parameters and a large number of labels is needed for a small character set (unlike in my original example). @graipher has the better solution in that respect. – Grismar Nov 20 '19 at 3:45
• Of course! I agree. We just have to explore new possibilites, right? :D – Srivaths Nov 20 '19 at 3:59

I thought I might compliment the other answers with an approach that follows the OP intuition closer.

I made it recursive, and factored out the creation of the sequence to a helper function :

def nth_label(n,symbols,accumulator=""):
q = n // len(symbols)
m = n % len(symbols)
if q==0:
return symbols[m]+accumulator
else:
return nth_label(q-1,symbols,symbols[m]+accumulator)

def generate_labels():
i = 0
while True:
yield nth_label(i, "abcdefghijklmnopqrstuvwxyz")
i += 1


Please be aware I just tested the equivalent javascript, not this python version!

Note that though this uses a recursive function, the depth of the recursion is only logarithmic on the number, with the base being the number of symbols (so a small number of recursions in practice).

It's easy to convert it to an iterative function, if a little less elegant IMO. It might be easier to see how this is different from itertools.product in the explicitly iterative version:

def nth_label(n,symbols):
result = ""
q = n // len(symbols)
m = n % len(symbols)
while q>0:
result = symbols[m]+result
n = q - 1
q = n // len(symbols)
m = n % len(symbols)

return symbols[m]+result

def generate_labels():
i = 0
while True:
yield nth_label(i, "abcdefghijklmnopqrstuvwxyz")
i += 1


It's proportional to log_k of n, where k is the number of symbols, in both space and time.

Sorry for the previous errors, this one is tested ;)

• Yeah, it basically codes out what @Graipher also provided as a solution; your recursive solution takes the place of the itertools.product and your generate_labels routine is the outer loop increasing the count. Thanks for contributing though, it may provide some additional insight to people that aren't familiar with those Python library functions. I updated your code to follow Python naming conventions and fixed a bug in the 2nd line of your nth_label function and tested the code - it works. – Grismar Nov 21 '19 at 7:09
• @Grismar Not exactly, though. The nthLabel function doesn't take a concatenation of the symbols, just a single copy. If I read his code correctly, he passes a list that gets bigger on each iteration? My code does what you did as close as possible, I just simplified the part that looked overly complex to you originally. – fede s. Nov 21 '19 at 17:46
• @Grimar PS: your edit was rejected by the review queue, I'll change those names, not much of a pythonista myself sorry – fede s. Nov 21 '19 at 17:49
• @Grismar I've updated the answer, to make it more obvious how this differs from itertools.product. – fede s. Nov 22 '19 at 1:28