9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What is one of the numbers/letter combinations being skipped? \$\endgroup\$ – Graipher Nov 19 at 8:38
  • 1
    \$\begingroup\$ @Graipher he probably meant to say that no letter maps to number zero. \$\endgroup\$ – slepic Nov 19 at 11:15
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Grismar Nov 20 at 2:53
  • 2
    \$\begingroup\$ Is this bijective base-26, as used in many spreadsheets ? \$\endgroup\$ – David Cary Nov 22 at 2:53
  • 1
    \$\begingroup\$ You're right @DavidCary, thanks for putting a name to it - I wasn't aware. \$\endgroup\$ – Grismar Nov 22 at 22:26
16
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Grismar Nov 20 at 3:45
  • \$\begingroup\$ Of course! I agree. We just have to explore new possibilites, right? :D \$\endgroup\$ – Srivaths Nov 20 at 3:59
0
\$\begingroup\$

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 ;)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Grismar Nov 21 at 7:09
  • \$\begingroup\$ @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. \$\endgroup\$ – fede s. Nov 21 at 17:46
  • \$\begingroup\$ @Grimar PS: your edit was rejected by the review queue, I'll change those names, not much of a pythonista myself sorry \$\endgroup\$ – fede s. Nov 21 at 17:49
  • \$\begingroup\$ @Grismar I've updated the answer, to make it more obvious how this differs from itertools.product. \$\endgroup\$ – fede s. Nov 22 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.