CODEWITHSUNDEEP
pythonlist
helpimlost
helpimlost

Reputation: 49

How to create brute force program that generates all possible combinations of a list up to an upper bound?

I have to create a function that takes accepts an upper bound list and returns a list with all possible combinations up to the upper bound. For example entering the list [1, 1, 2] would yield: 

[ [ 0 , 0 , 0 ] , 
[ 0 , 0 , 1 ] , 
[ 0 , 0 , 2 ] , 
[ 0 , 1 , 0 ] , 
[ 0 , 1 , 1 ] ,
[ 0 , 1 , 2 ] , 
[ 1 , 0 , 0 ] , 
[ 1 , 0 , 1 ] , 
[ 1 , 0 , 2 ] , 
[ 1 , 1 , 0 ] , 
[ 1 , 1 , 1 ] , 
[ 1 , 1 , 2 ] , ]

So far I have this:

def bounded_lists(upper_bound):
    start = [0] * len(upper_bound)
    print(start)
    while start != upper_bound:
        for i in range(1, len(upper_bound)+ 1):
            while start[-i] < upper_bound[-i]:
                start[-i] = start[-i] + 1
                print(start)
            start[-i] = 0
        break

However, it only returns: 

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[1, 0, 0]

Upvotes: 0

Views: 231

Answers (1)

P3qiUB
P3qiUB

Reputation: 156

You can use the standard library itertools

from itertools import product

def bounded_lists(upper_bound):
    return list(product(*[range(ub + 1) for ub in upper_bound]))

This works like this:

>>> bounded_lists([1, 1, 2])
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2)]

Update: If you don't feel comfortable using additional libraries, you can try to do it recursively.

def bounded_lists(upper_bound):
    result = []

    if len(upper_bound)== 0:
        result = []
    elif len(upper_bound)==1:
        result = [[i] for i in range(upper_bound[0] + 1)]
    else:
        first_bound = upper_bound[0]
        other_bound = upper_bound[1:]
        for i in range(first_bound + 1):
            for lst in bounded_lists(other_bound):
                result.append([i] + lst)
    return result

Upvotes: 5

Related Questions