Divide a set of strings into those which contain "a" and those which don't I am beginning to learn Python on my own through edX and I was given this basic problem: "Given a list of cities, separate the list into two lists, namely one with cities containing the letter 'a' in their name and one with cities not containing the letter 'a'."

This is my approach. It works, but I can't help but feel like there is a much more concise way to get this result. If anybody could offer some other methods I would be interested:

cities = ["New York", "Shanghai", "Munich", "Tokyo", "Dubai", "Mexico City", "São Paulo", "Hyderabad"]

a_city, no_a_city = [],[]
for city in cities:
    for x in range(0, len(city)):
        if city[x] == "a":
            a_city.append(city)
            break
        else:
            if x == len(city) - 1:
                no_a_city.append(city)



print("a_city:", a_city)
print("no_a_city:", no_a_city)


I am also interested in learning more about the interaction between nested loops/conditionals and complexity if anybody has some resources.
This usecase is actually covered by one of the itertools recipes. itertools is a package in the Python standard library that supplies fast and efficient tools for iterating over things or creating certain iterable things (like the combination of all pairs and such). It is an often used library and well worth it to get acquainted with.

The recipe is as follows:


from itertools import filterfalse, tee

def partition(pred, iterable):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --&gt; 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)



In your specific case you would use it like this:

if __name__ == "__main__":    
    cities = ["New York", "Shanghai", "Munich", "Tokyo", "Dubai", "Mexico City", "São Paulo", "Hyderabad"]
    no_a_city, a_city = map(list, partition(lambda city: "a" in city, cities))
    print("a_city:", a_city)
    print("no_a_city:", no_a_city)


The map(list, ...) part is needed because what the partition function returns are generators that generate values on the fly. They can be consumed into a list.

The predicate used is a lambda function, an anonymous function which in this case returns truthy or falsy values. It is used to test each element of the iterable.

Instead of manually iterating over each name (even worse, over each index of each name, have a look at Loop Like A Native), I used the fact that strings support the in operator.

I also added a if __name__ == "__main__": guard to allow importing from this script from another script.



One thing you could have used in your code is the fact that for loops have an optional else clause which is run if no break statement interrupted the loop:

a_city, no_a_city = [],[]
for city in cities:
    for char in city:
        if char == "a":
            a_city.append(city)
            break
    else:
        no_a_city.append(city)




As for complexity, this has the same complexity as your code. You have two nested for loops, making this on average \$\mathcal{O}(nk)\$ with \$n\$ being the number of cities and \$k\$ being the average length of the city names.

The in operator for strings is \$\mathcal{O}(k)\$ (it is just the same loop you wrote, but probably written in C) and it is used once per city. However, due to the tee my code iterates twice over the cities, so would be \$\mathcal{O}(2nk)\$, which in terms of algorithmic complexity is also \$\mathcal{O}(nk)\$.