How to generate every combination inside a list subject to constraints in python?

user_1596433 0
Viewed 341

I have a problem where I need to generate list of every combination possible based on given constraints and I am not sure of any approach that might help. I have a list with 12 slots available and I need to populate each slot x and y subject to constraints mentioned below.

x >= 7, x <= 9
y >= 4, y <= 9
list = [0,0,0,0,0,0,0,0,0,0,0,0]

I am struggling to formulate the problem correctly but I need a solution where list can have continous value of x from 1 to atleast 7 and maximum 9 and y from 1 to atleast 4 and maximum 9 and list should not have any 0. So one of the solution could be:

# Solution 1 as x has occupied 9 continuous slots and y occupied 4
x = 1,1,1,1,1,1,1,1,1,0,0,0
y = 0,0,0,0,0,0,0,0,1,1,1,1
list= [1,1,1,1,1,1,1,1,2,1,1,1] 

# Solution 2 as x has occupied 8 continuous slots and y occupied 7 with no zero left
x = 0,0,0,0,1,1,1,1,1,1,1,1
y = 1,1,1,1,1,1,1,0,0,0,0,0
list= [1,1,1,1,2,2,2,1,1,1,1,1]

I need to generate every possible combination in the above fashion. Can someone please help or atleast give me some pointer on how can I achieve this in python ? Thanks

data-science pandas python
3 Answers

Just following your description of the problem naively, one simple approach would be to loop over each of the pairs of lengths, as well as each possible starting index of each of the lists:

import numpy as np

def find_all():
    for x in range(7, 10):
        for y in range(4, 10):
            for xs in range(13 - x):
                for ys in range(13 - y):
                    a = np.zeros(12, int)
                    a[xs:xs+x] += 1
                    a[ys:ys+y] += 1
                    if 0 not in a:
                        yield x, y, xs, ys, a

list(find_all())

Output:

[(7, 5, 0, 7, array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])),
 (7, 5, 5, 0, array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])),
 (7, 6, 0, 6, array([1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1])),
 (7, 6, 5, 0, array([1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1])),
 (7, 7, 0, 5, array([1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1])),
 (7, 7, 5, 0, array([1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1])),
 (7, 8, 0, 4, array([1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1])),
 (7, 8, 5, 0, array([1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1])),
 (7, 9, 0, 3, array([1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1])),
 (7, 9, 5, 0, array([1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1])),
 (8, 4, 0, 8, array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])),
 (8, 4, 4, 0, array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])),
 (8, 5, 0, 7, array([1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1])),
 (8, 5, 4, 0, array([1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1])),
 (8, 6, 0, 6, array([1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1])),
 (8, 6, 4, 0, array([1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1])),
 (8, 7, 0, 5, array([1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1])),
 (8, 7, 4, 0, array([1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1])),
 (8, 8, 0, 4, array([1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1])),
 (8, 8, 4, 0, array([1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1])),
 (8, 9, 0, 3, array([1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1])),
 (8, 9, 4, 0, array([1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1])),
 (9, 4, 0, 8, array([1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1])),
 (9, 4, 3, 0, array([1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1])),
 (9, 5, 0, 7, array([1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1])),
 (9, 5, 3, 0, array([1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1])),
 (9, 6, 0, 6, array([1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1])),
 (9, 6, 3, 0, array([1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1])),
 (9, 7, 0, 5, array([1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1])),
 (9, 7, 3, 0, array([1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1])),
 (9, 8, 0, 4, array([1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1])),
 (9, 8, 3, 0, array([1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1])),
 (9, 9, 0, 3, array([1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1])),
 (9, 9, 3, 0, array([1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1]))]

For example, in the first output, the x-array has length 7 and starts at position 5, while the y-array has length 5 and starts at position 7.

This is of course horribly inefficient for larger values of the inputs, and the exact same thing can be achieved through

def find_all():
    for x in range(7, 10):
        for y in range(max(12 - x, 4), 10):
            a = np.ones(12, int)
            a[12-y:x] = 2
            yield x, y, 0, 12-y, a
            yield x, y, 12-x, 0, a[::-1]

list(find_all())
user_50852110

IIUC:

for i in range(7,10):
    x = np.repeat((1,0), (i, 12-i))
    for j in range(4,i):
        y = np.repeat((0,1), (j, 12-j))

        a = x + y

        print(x,y,a)

Output:

[1 1 1 1 1 1 1 0 0 0 0 0] [0 0 0 0 1 1 1 1 1 1 1 1] [1 1 1 1 2 2 2 1 1 1 1 1]
[1 1 1 1 1 1 1 0 0 0 0 0] [0 0 0 0 0 1 1 1 1 1 1 1] [1 1 1 1 1 2 2 1 1 1 1 1]
[1 1 1 1 1 1 1 0 0 0 0 0] [0 0 0 0 0 0 1 1 1 1 1 1] [1 1 1 1 1 1 2 1 1 1 1 1]
[1 1 1 1 1 1 1 1 0 0 0 0] [0 0 0 0 1 1 1 1 1 1 1 1] [1 1 1 1 2 2 2 2 1 1 1 1]
[1 1 1 1 1 1 1 1 0 0 0 0] [0 0 0 0 0 1 1 1 1 1 1 1] [1 1 1 1 1 2 2 2 1 1 1 1]
[1 1 1 1 1 1 1 1 0 0 0 0] [0 0 0 0 0 0 1 1 1 1 1 1] [1 1 1 1 1 1 2 2 1 1 1 1]
[1 1 1 1 1 1 1 1 0 0 0 0] [0 0 0 0 0 0 0 1 1 1 1 1] [1 1 1 1 1 1 1 2 1 1 1 1]
[1 1 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 1 1 1 1 1 1 1 1] [1 1 1 1 2 2 2 2 2 1 1 1]
[1 1 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 0 1 1 1 1 1 1 1] [1 1 1 1 1 2 2 2 2 1 1 1]
[1 1 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 0 0 1 1 1 1 1 1] [1 1 1 1 1 1 2 2 2 1 1 1]
[1 1 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 0 0 0 1 1 1 1 1] [1 1 1 1 1 1 1 2 2 1 1 1]
[1 1 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 0 0 0 0 1 1 1 1] [1 1 1 1 1 1 1 1 2 1 1 1]
user_42384080

The following should produce what you're looking for:

def get_array(arr_min, arr_max, length, end=False):
    arr_full = np.tril(np.ones((length, length)))
    if end:
        arr_full = arr_full[:, ::-1]
    arr_row_tot = arr_full.sum(axis=1)
    row_sel = (arr_row_tot >= arr_min) & (arr_row_tot <= arr_max)
    arr = arr_full[row_sel, :]
    return arr

def get_combos(x_min_max, y_min_max, length=12):
    X = get_array(*x_min_max, length)
    Y = get_array(*y_min_max, length, end=True)
    X = np.expand_dims(X, 1)
    combos = (X + Y).reshape(-1, length).astype("int")
    lists = [list(sub_arr) for sub_arr in combos]
    x_y_vals = [
        {"x": x, "y": y}
        for x in range(x_min_max[0], x_min_max[1] + 1)
        for y in range(y_min_max[0], y_min_max[1] + 1)
    ]
    return list(zip(x_y_vals, lists))

Some examples:

get_combos((4, 9), (5, 7), 12) output:

[({'x': 4, 'y': 5}, [1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 4, 'y': 6}, [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]),
 ({'x': 4, 'y': 7}, [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]),
 ({'x': 5, 'y': 5}, [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 5, 'y': 6}, [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]),
 ({'x': 5, 'y': 7}, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
 ({'x': 6, 'y': 5}, [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]),
 ({'x': 6, 'y': 6}, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
 ({'x': 6, 'y': 7}, [1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1]),
 ({'x': 7, 'y': 5}, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
 ({'x': 7, 'y': 6}, [1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]),
 ({'x': 7, 'y': 7}, [1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1]),
 ({'x': 8, 'y': 5}, [1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1]),
 ({'x': 8, 'y': 6}, [1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1]),
 ({'x': 8, 'y': 7}, [1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1]),
 ({'x': 9, 'y': 5}, [1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1]),
 ({'x': 9, 'y': 6}, [1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]),
 ({'x': 9, 'y': 7}, [1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1])]

get_combos((2, 6), (2, 5), 12) output:

[({'x': 2, 'y': 2}, [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]),
 ({'x': 2, 'y': 3}, [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]),
 ({'x': 2, 'y': 4}, [1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]),
 ({'x': 2, 'y': 5}, [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 3, 'y': 2}, [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1]),
 ({'x': 3, 'y': 3}, [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1]),
 ({'x': 3, 'y': 4}, [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1]),
 ({'x': 3, 'y': 5}, [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 4, 'y': 2}, [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1]),
 ({'x': 4, 'y': 3}, [1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1]),
 ({'x': 4, 'y': 4}, [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]),
 ({'x': 4, 'y': 5}, [1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 5, 'y': 2}, [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1]),
 ({'x': 5, 'y': 3}, [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]),
 ({'x': 5, 'y': 4}, [1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]),
 ({'x': 5, 'y': 5}, [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1]),
 ({'x': 6, 'y': 2}, [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]),
 ({'x': 6, 'y': 3}, [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1]),
 ({'x': 6, 'y': 4}, [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]),
 ({'x': 6, 'y': 5}, [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1])]
user_45857130
Related