how to create all combinations of n numbers by being able to use numbers multiple times recursively

Question

as an example I have numbers 0 and 255. I want combinations that would look like this

[[0, 0], [0, 255], [255, 0], [255, 255]]

my current code looks like this, where "a" is the list of numbers, it could be 2 or more.

def combinations(a):
    if len(a) == 0:
        return [[]]
    final = []
    for i in combinations(a[1:]):
        final += [i, i+[a[0]]]
    return final

but it instead gives this output [[], [0], [255], [255, 0]]

I am looking for a way to solve it recursively without using any libraries.

if your list is [0, 255] then [0,0] and [255, 255] are not combinations in that list — d_kennetz, Dec 16 '21 at 22:52
@EduardoTolmasquim yes, meaning combinations can get quite large in numbers. — Saba, Dec 16 '21 at 22:54
So the sizes of the lists that are returned are to be the same as the size of the list with possible values? Or is that pure coincidence in your example? — trincot, Dec 16 '21 at 22:54
@trincot yes exactly, if there were 3 numbers, all "combinations" would be with the length of 3 — Saba, Dec 16 '21 at 22:55
What you are looking for is called a Cartesian product - specifically, of the same list with itself multiple times. See the linked duplicate. `itertools` is in the standard library and unless you are trying to teach yourself to write recursive algorithms, you don't have a realistic reason to avoid it. — Karl Knechtel, Dec 16 '21 at 22:57
@KarlKnechtel wherever i am executing this task, I cant use any libraries at all. I found solutions with that library before i came here, but i just cant use it. — Saba, Dec 16 '21 at 22:58
Why can't you use it? If it's for homework then a) you should ask your instructor for help first; b) read https://meta.stackoverflow.com/questions/334822. — Karl Knechtel, Dec 16 '21 at 23:00

score 2 · Accepted Answer · answered Dec 16 '21 at 22:45

You can use itertools for that:

from itertools import product
lst = [0, 255]
[p for p in product(lst, repeat=2)]
# [(0, 0), (0, 255), (255, 0), (255, 255)]

Since you do not want to import libraries, you can also look up the documentation of itertools and use the function directly:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)


lst = [0, 255]
[p for p in product(lst, repeat=2)]

how to create all combinations of n numbers by being able to use numbers multiple times recursively

1 Answers1