1

I'm trying to build a function that:

  • accepts as an argument a list of positive integers of length n and
  • returns a list of all lists of length n consisting of non-negative integers with the following property:
    • for a list lst it holds that for all indices i, lst[i] ≤ upper bound[i]

For example, if the input list was [1, 1, 2], then the output would be

[ [ 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 ] , ]

This is how far I've gotten:

def bounded_list(ub):
    f = len(ub) * [0]
    l = ub
    res = [f]

    while res[-1] != l:
        res += [lex_suc1(res[-1], ub)]

    return res


def lex_suc1(lst, ub):
    res = lst[:]

    i = len(res) - 1
    while res[i] == ub[i]:
        res[i] = 0
        i -= 1

    res[i] = ub[i]
    return res

which gives the output:

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

I'm not able to understand how to include the missing lists, any help woul be great.

smci
  • 32,567
  • 20
  • 113
  • 146
lakshjaisinghani
  • 171
  • 1
  • 12
  • Related: [Cartesian product of iterators](https://stackoverflow.com/questions/12093364/cartesian-product-of-large-iterators-itertools) – smci Apr 30 '19 at 12:15
  • You want a Cartesian product of individual `range`s. And [`range`](https://docs.python.org/3.7/library/stdtypes.html?highlight=range#range) is an iterable which yields all the integers in the given range. – smci Apr 30 '19 at 12:32

3 Answers3

3

this is an option:

from itertools import product

for lst in product(range(2), range(2), range(3)):
    print(lst)

note that your list [1, 1, 2] translates to range(2), range(2), range(3) here.

or more directly:

res = list(product(range(2), range(2), range(3)))
# [(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)]

or even:

lst = [1, 1, 2]
res = list(product(*(range(i+1) for i in lst)))
hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
2

You should take a look at itertools package and list comprehensions.

Then a solution is:

def f(upper_bounds):
    return list(itertools.product(*(range(ub+1) for ub in upper_bounds)))
olinox14
  • 6,177
  • 2
  • 22
  • 39
  • Why won't the syntax `itertools.product(*range(ub+1) for ub in upper_bounds)` work, i.e. `itertools.product` won't itself accept subiterators? Why do we need to use `[...]` to force expansion of the subiterators into lists? – smci Apr 30 '19 at 12:11
  • As far as I know the syntax you proposed is invalid because of the `*` in first position: on what should python apply the upacking? on `range()` or on the whole iterator? – olinox14 Apr 30 '19 at 12:17
  • I know that's a syntax error, I'm asking whether we can do that more elegantly than *\[splatting unpacking of all the subiterators? because as [Cartesian product of iterators](https://stackoverflow.com/questions/12093364/cartesian-product-of-large-iterators-itertools) points out can blow out memory. – smci Apr 30 '19 at 12:19
  • 1
    @smci instead of unpacking a list `*[...]` you can unpack a generator expression `*(...)`. although memory-wise this will not be much of an improvement here... – hiro protagonist Apr 30 '19 at 12:24
  • Ah ok, extra brackets needed. I suspect `*(...)` is cleaner and more memory efficient than `*[...]` Thanks for teaching me! – smci Apr 30 '19 at 12:26
  • No, `itertools.product(*(range(ub+1) for ub in upper_bounds))`. Note that's `*(range ...)` not `*[range ...]` – smci Apr 30 '19 at 12:30
  • @hiroprotagonist: Ooops. Duh. Anyway yes I think `*(...)` is better than `*[...]` – smci Apr 30 '19 at 12:33
  • Yeah ok, a geneator should be better, but if and only if the itertools method do not convert it to a list immediatly after that, and it seems it does according to the [definition here](https://docs.python.org/3.7/library/itertools.html#itertools.product... anyway, I'll update my answer. – olinox14 Apr 30 '19 at 15:12
0

You can use itertools.product for this.

from  itertools import product
li = [1, 1, 2]

#Generate a list of possible numbers to generate the output from the given list
iters = [list(range(item+1)) for item in li]
#[[0, 1], [0, 1], [0, 1, 2]]

#Generate all possible combinations of these lists
print(list(product(*iters)))

The output will then be.

[(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)]
Devesh Kumar Singh
  • 20,259
  • 5
  • 21
  • 40