# Library to Help Loop with Generators

I found I need to loop through a list to create a brute force algorithm. Therefore, I decided to make a library, but to generalize the result by using a generator. There are three cases which is every single element, every pair of elements, and every triple of elements. The cases store a variable which contains the generator function. Currently, the generator is required to be nested with no parameters inside a function which takes the data structure as a parameter. Therefore, the average space complexity is O(1) in the three cases. The code is below.



def test_generator():
yield "a"
yield "b"

def singles(generator):
"""
average time: O(n) where n is the number of yields from generator
average space: O(1)
"""
for at in generator():
yield at

def test_singles():
assert list(singles(test_generator)) == ["a", "b"]

def pairs(generator):
"""
average time: O(n * n) where n is the number of yields from generator
average space: O(1)
"""
first_generator = generator
second_generator = generator
for first in first_generator():
second_generator = generator
for second in second_generator():
yield first, second

def test_pairs():
assert list(pairs(test_generator)) == [("a", "a"), ("a", "b"), ("b", "a"), ("b", "b")]

def triples(generator):
"""
average time: O(n * n * n) where n is the number of yields
average sapce: O(1)
"""
first_generator = generator
second_generator = generator
third_generator = generator
for first in first_generator():
second_generator = generator
for second in second_generator():
third = third_generator
for third in third_generator():
yield first, second, third

def test_triples():
assert list(triples(test_generator)) == [("a", "a", "a"), ("a", "a", "b"), ("a", "b", "a"),
("a", "b", "b"), ("b", "a", "a"), ("b", "a", "b"), ("b", "b", "a"), ("b", "b", "b")]

def tests():
test_singles()
test_pairs()
test_triples()

if __name__ == "__main__":
tests()


# Unnecessary variables

def pairs(generator):
"""
average time: O(n * n) where n is the number of yields from generator
average space: O(1)
"""
first_generator = generator
second_generator = generator
for first in first_generator():
second_generator = generator
for second in second_generator():
yield first, second


The value of second_generator does not change in the loop. Therefore, the assignment to second_generator in the loop may be omitted.

def pairs(generator):
"""
average time: O(n * n) where n is the number of yields from generator
average space: O(1)
"""
first_generator = generator
second_generator = generator
for first in first_generator():
for second in second_generator():
yield first, second


In fact, the value of generator never changes, so first_generator and second_generator always equal generator. Thus first_generator and second_generator are redundant variables and may be omitted entirely.

def pairs(generator):
"""
average time: O(n * n) where n is the number of yields from generator
average space: O(1)
"""
for first in generator():
for second in generator():
yield first, second


Identical improvements may be applied to the triples function.

# Useless assignment

            third = third_generator
for third in third_generator():
yield first, second, third


The assignment to third before the loop is immediately overwritten by the for ... in ... loop statement, which also assigns values to third.

What you are doing is basically equivalent to itertools.product, you should check it out.

• From the documentation, "Before product() runs, it completely consumes the input iterables, keeping pools of values in memory to generate the products. Accordingly, it is only useful with finite inputs." This means the average space would not remain $O(1)$. Oct 12, 2021 at 17:51