Incrementing a string in python

Question

I was trying to write a function that would return the incrementation of a string. For example, if the input were "xx", it should return [xx, xy, xz, ya, yb, ..., zz, aa]. The function for incrementing a single character was no problem

def incrementChar(char):
    if char == "z":
        return "a"
    else:
        return chr(ord(char)+1)

and I tried writing a recursive function that would take the last character of the input increment that one all the way up to "z", take the second to last character of the input and increment it by one while letting the last character run from "a" to "z" again.

I tried this code

def incrementString(string):
    possibilities = []
    for i in range(len(string)-1, -1, -1):
        if i == len(string)-1 and string[i] != "z":
              while string[i] != "z": 
                possibilities.append(string.replace(string[i], incrementChar(string[i])))
                string = string.replace(string[i], incrementChar(string[i]))
                print(string)        
        else:
            incrementString(string[i:])
    return possibilities

and the first part works, it does run the last character to z and then increases the second to last by one, but starts increasing all characters at once and breaks in an infinite loop.

I'm sure that I'm overseeing something quite obvious, (the issue has to be that the second to last character is not being fixed while the last loops through the alphabet) maybe someone could help me with it...

Thanks!

RufusVS · Accepted Answer · 2021-03-27 18:01:19Z

I liked @jdowner answer, but was interested in performance, so I tried 3 ways:

import string
import timeit

# The original characters and their subsequent character
orig = string.ascii_lowercase
tran = orig[1:] + orig[0]

# make a translate table
trantable = str.maketrans(orig,tran)

# make a translate dictionary
trandict = dict(zip(orig,tran))

def inc(text):
    if not text:
        return "a"

    if text[-1] == "z":
        return inc(text[:-1]) + "a"

    return text[:-1] + tran[orig.find(text[-1])]

def inc2(text):
    if not text:
        return "a"

    if text[-1] == "z":
        return inc(text[:-1]) + "a"

    return text[:-1] + text[-1].translate(trantable)

def inc3(text):
    if not text:
        return "a"

    if text[-1] == "z":
        return inc(text[:-1]) + "a"

    return text[:-1] + trandict[text[-1]]

for incfunc in [inc,inc2,inc3]:
    print (f"test function {incfunc.__name__}")
    print (timeit.timeit(stmt='incfunc("teststring")', number=1000000, globals=globals()))

Which returned:

test function inc
2.013159
test function inc2
1.9140723000000004
test function inc3
1.6101508999999998

jdowner · Accepted Answer · 2021-03-27 16:39:04Z

1

This is how I would go about it. A simple mapping from the original character to the translated character and handle the special cases when the last character is a 'z' or there are no characters before the one being processed.

import string

# The original characters and their subsequent character
orig = string.ascii_lowercase
tran = orig[1:] + orig[0]


def inc(text):
    if not text:
        return "a"

    if text[-1] == "z":
        return inc(text[:-1]) + "a"

    return text[:-1] + tran[orig.find(text[-1])]

answered Mar 27, 2021 at 16:39

jdowner

7461 gold badge8 silver badges23 bronze badges

1 Comment

RufusVS Over a year ago

Perhaps creating a translation dictionary might be slightly faster than the find method.

Collectives™ on Stack Overflow

Incrementing a string in python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related