2
\$\begingroup\$

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()
\$\endgroup\$
0
0
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ 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)\$. \$\endgroup\$
    – AJNeufeld
    Oct 12 at 17:51

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.