Library to Help Loop with Generators

Question

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

Answer 1

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.

Answer 2

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

• AJNeufeld: 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)\$.