[Python]: generate and array of all possible combinations

Question

I have a very straightforward combination problem. I have two arrays (a and b). Array a indicates all the values one of the three slots in array b can take on. Each slot in array b can have a value between 1 and 5. An example of which would be [1, 4, 5]. I would like to generate an array (c) with all possible combinations. I like to extend the basic example larger arrays.

Input:

a = [1, 2, 3, 4, 5]
b = [1, 2, 3]

Output:

c = [[1, 1, 1], [1, 1, 2],[1, 1, 3], [1, 1, 4], [1, 1, 5],
     [1, 2, 1], [1, 2, 2],[1, 2, 3], [1, 2, 4], [1, 2, 5],
     [1, 3, 1], [1, 3, 2],[1, 3, 3], [1, 3, 4], [1, 3, 5],
     [1, 4, 1], [1, 4, 2],[1, 4, 3], [1, 4, 4], [1, 4, 5],
     [1, 5, 1], [1, 5, 2],[1, 5, 3], [1, 5, 4], [1, 5, 5],
     [2, 1, 1], [2, 1, 2],[2, 1, 3], [2, 1, 4], [2, 1, 5],
     [2, 2, 1], [2, 2, 2],[2, 2, 3], [2, 2, 4], [2, 2, 5],
     [2, 3, 1], [2, 3, 2],[2, 3, 3], [2, 3, 4], [2, 3, 5],
     [2, 4, 1], [2, 4, 2],[2, 4, 3], [2, 4, 4], [2, 4, 5],
     [2, 5, 1], [2, 5, 2],[2, 5, 3], [2, 5, 4], [2, 5, 5],
     [3, 1, 1], [3, 1, 2],[3, 1, 3], [3, 1, 4], [3, 1, 5],
     [3, 2, 1], [3, 2, 2],[3, 2, 3], [3, 2, 4], [3, 2, 5],
     [3, 3, 1], [3, 3, 2],[3, 3, 3], [3, 3, 4], [3, 3, 5],
     [3, 4, 1], [3, 4, 2],[3, 4, 3], [3, 4, 4], [3, 4, 5],
     [3, 5, 1], [3, 5, 2],[3, 5, 3], [3, 5, 4], [3, 5, 5],
     [4, 1, 1], [4, 1, 2],[4, 1, 3], [4, 1, 4], [4, 1, 5],
     [4, 2, 1], [4, 2, 2],[4, 2, 3], [4, 2, 4], [4, 2, 5],
     [4, 3, 1], [4, 3, 2],[4, 3, 3], [4, 3, 4], [4, 3, 5],
     [4, 4, 1], [4, 4, 2],[4, 4, 3], [4, 4, 4], [4, 4, 5],
     [5, 5, 1], [5, 5, 2],[5, 5, 3], [5, 5, 4], [5, 5, 5],
     [5, 1, 1], [5, 1, 2],[5, 1, 3], [5, 1, 4], [5, 1, 5],
     [5, 2, 1], [5, 2, 2],[5, 2, 3], [5, 2, 4], [5, 2, 5],
     [5, 3, 1], [5, 3, 2],[5, 3, 3], [5, 3, 4], [5, 3, 5],
     [5, 4, 1], [5, 4, 2],[5, 4, 3], [5, 4, 4], [5, 4, 5],
     [5, 5, 1], [5, 5, 2],[5, 5, 3], [5, 5, 4], [5, 5, 5]]

Solution for the problem above:

d = []
for i in range(len(a)):
    for j in range(len(a)):
        for k in range(len(a)):
            e = []
            e.append(i+1)
            e.append(j+1)
            e.append(k+1)
            d.append(e)

I am looking for a more generic way. One which can accommodate larger arrays (see below) without the need to use a nested for loop structure. I searched for a comparable example, but was unable to find one on stackoverflow.

Input:

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Take a look at python [itertools](https://docs.python.org/2/library/itertools.html). The combination method does what I think you are looking for. — dlshriver, Apr 22 '16 at 21:21
From your description, I also don't think you need an array for `b`, just an integer value that specifies the array's length — wilkesybear, Apr 22 '16 at 21:22
I had a similar question when I ran a MonteCarlo simulation over a number of toleranced variables, but I found that it didn't make sense to generate an array of all possible combinations, when it was so easy (see your own code) to generate those combinations on the fly. — roadrunner66, Apr 22 '16 at 21:22
This looks a lot more like the Cartesian product to me than combinations, in which case it's a duplicate of many, many previous questions. — DSM, Apr 22 '16 at 21:26
Possible duplicate? http://stackoverflow.com/questions/1208118/using-numpy-to-build-an-array-of-all-combinations-of-two-arrays — Adib, Apr 22 '16 at 21:34
FYI, the body of your for loop could be written `d.append([i+1, j+1, k+1])`. Also you need to use better variable names. — Alex Hall, Apr 22 '16 at 22:22

Delgan · Accepted Answer · 2016-04-22T21:28:59.210

4

You are looking for itertools.product().

a = [1, 2, 3, 4, 5]
b = 3  # Actually, you just need the length of the array, values do not matter

c = itertools.product(a, repeat=b)

Note that this returns an iterator, you may need to cast it using list() but be aware this can take forever and highly consume memory if the sizes grow.

edited Apr 22 '16 at 21:28

answered Apr 22 '16 at 21:22

Delgan

18,571
11
90
141

score 2 · Answer 2 · answered Apr 22 '16 at 21:31

In the general case, you should of course use the itertools module, in this particular case itertools.product, as explained in the other answer.

If you want to implement the function yourself, you can use recursion to make it applicable to any array sizes. Also, you should probably make it a generator function (using yield instead of return), as the result could be rather long. You can try something like this:

def combinations(lst, num):
    if num > 0:
        for x in lst:
            for comb in combinations(lst, num - 1):
                yield [x] + comb
    else:
        yield []

[Python]: generate and array of all possible combinations

2 Answers2