2 views

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

by (41.4k points)
edited

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.

by (36.8k points)

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