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

Question

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

Answer 1

Here is an approach that will loop over each of the pairs of lengths and 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]))]

Here,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.So, for larger values of input this is inefficient.

This exact thing can be done with the below code:

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())

If you wish to learn more about how to use python for data science, then go through this data science python course by Intellipaat for more insights.

Answer 2

You can use the loop for each pair of length and also fir each possible index of each list like this:

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]))]

Let us understand the first output:

the length of the x-axis has 7 and its beginning position is 5 and the y-axis length is 5 and begins at position7. So this leads to large values in the input and to extract the value use need to use the below code:

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())

 If you want to know more about the Data Science then do check out the following Data Science which will help you in understanding Data Science from scratch