Ygtjki

I'm looking for help on the following problem. I have a small program that is part of a much larger program, I need to loop through every combination of an array of number from 1 to 10 (maybe more or less) in the same way itertools works. However because I have certain restrictions, I have a need to skip a large number of these combinations to save time as this could potentially get very large.

Here is my program

combination = [-1, -1, -1, -1]
len_combination = len(combination)

max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
len_index = len(max_at_index)

end = 0


def skip(depth):

 combination[depth] = combination[depth] + 1
 if combination[depth] == len_index:
 combination[depth] = 0

 for x in range(0, len_index):
 if combination[:depth + 1].count(x) > max_at_index[x]:

 return True

 return False


for i in range(0, len_index):

 if skip(0):
 continue

 for j in range(0, len_index):

 if skip(1):
 continue

 for k in range(0, len_index):

 if skip(2):
 continue

 for l in range(0, len_index):

 if skip(3):
 continue

 print(combination)

This example has 4 items each looping from 0 to 9, ([0, 0, 0, 0] to [9, 9, 9, 9]). However my variable max_at_index is restricting the count of values allowed in the array at each index. Here we are allowed 0 0s, 2 1s, 2 2s, 1 3s etc. This is working well and I can even expand or shrink the max_at_index array.

What I cant figure out how to do is make the nested for loop recursive so I can expand or shrink the size of combination to have more or less elements.

Thank you in advance.

EDIT:
As requested, some explanation to my logic

Consider the following list of costs

[
[1, 2, 3, 4, 5, 6, 0, 8, 9],
[10, 11, 12, 0, 14, 15, 16, 17, 18, 19],
[0, 21, 22, 23, 24, 25, 26, 27, 28, 29],
[30, 0, 32, 33, 34, 35, 0, 37, 38, 0]
]

I have to generate the smallest possible total when picking one number from each array where...

• The number from each array can not be 0


• The index of each chosen number can not exceed a given limit (i.e no more than 3 from index 2)


• The number of numbers chosen from index 0 must reach a limit (for
  example 2 must come from index 0) or the next highest possible.

This part I have figured out too. If I loop each and every single possible combination from 0,0,0,0 to 9,9,9,9 I can test to see if it meets the above. I just need to avoid looping every combination as most of them will be useless and it will grow large

I think this is one possible implementation:

def bounded_comb(max_at_index, n):
 yield from _bounded_comb_rec(max_at_index, n, [0] * len(max_at_index), [])

def _bounded_comb_rec(max_at_index, n, counts, current):
 # If we have enough elements finish
 if len(current) >= n:
 yield tuple(current)
 else:
 # For each index and max
 for idx, m in enumerate(max_at_index):
 # If the max has not been reached
 if m > counts[idx]:
 # Add the index
 counts[idx] += 1
 current.append(idx)
 # Produce all combinations
 yield from _bounded_comb_rec(max_at_index, n, counts, current)
 # Undo add the index
 current.pop()
 counts[idx] -= 1

# Test
max_at_index = [0, 2, 1, 3]
n = 4
print(*bounded_comb(max_at_index, n), sep='n')

Output:

(1, 1, 2, 3)
(1, 1, 3, 2)
(1, 1, 3, 3)
(1, 2, 1, 3)
(1, 2, 3, 1)
(1, 2, 3, 3)
(1, 3, 1, 2)
(1, 3, 1, 3)
(1, 3, 2, 1)
(1, 3, 2, 3)
(1, 3, 3, 1)
(1, 3, 3, 2)
(1, 3, 3, 3)
(2, 1, 1, 3)
(2, 1, 3, 1)
(2, 1, 3, 3)
(2, 3, 1, 1)
(2, 3, 1, 3)
(2, 3, 3, 1)
(2, 3, 3, 3)
(3, 1, 1, 2)
(3, 1, 1, 3)
(3, 1, 2, 1)
(3, 1, 2, 3)
(3, 1, 3, 1)
(3, 1, 3, 2)
(3, 1, 3, 3)
(3, 2, 1, 1)
(3, 2, 1, 3)
(3, 2, 3, 1)
(3, 2, 3, 3)
(3, 3, 1, 1)
(3, 3, 1, 2)
(3, 3, 1, 3)
(3, 3, 2, 1)
(3, 3, 2, 3)
(3, 3, 3, 1)
(3, 3, 3, 2)

I didn't want to show anything fancy, but to give you the simplest answer for recursive loop (as that was your question)

combination = [-1, -1, -1, -1]
len_combination = len(combination)
max_depth = 3
max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
len_index = len(max_at_index)

end = 0

def skip(depth):

 combination[depth] = combination[depth] + 1
 if combination[depth] == len_index:
 combination[depth] = 0

 for x in range(0, len_index):
 if combination[:depth + 1].count(x) > max_at_index[x]:

 return True,combination # Needs to return the state of combination

 return False,combination # Needs to return the state of combination

def loop(depth,combination):
 if depth == max_depth:
 boolean, combination = skip(depth)
 if not(boolean):
 print (combination)
 return combination
 else:
 for i in range(0, len_index):
 boolean, combination = skip(depth)
 if not(boolean):
 loop(depth+1,combination)

loop(0,combination)

this is a try where i restrict construct a pool of values to select from (select_from) and then build the combinations:

from itertools import chain, combinations

max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]

select_from = list(chain.from_iterable(n * [i] for i, n in enumerate(max_at_index)))
# [1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9]

for comb in combinations(select_from, 4):
 print(comb)

this produces the combinaions sorted. if you need all the permutations as well, you need to do that afterwards (i use the set 'seen' here in order to avoid duplicates):

from itertools import chain, combinations, permutations

seen_comb = set()

select_from = list(chain.from_iterable(n * [i] for i, n in enumerate(max_at_index)))

for comb in combinations(select_from, 4):

 sorted_comb = tuple(sorted(comb))
 if sorted_comb in seen_comb:
 continue
 seen_comb.add(sorted_comb)

 seen_perm = set()

 for perm in permutations(comb):
 if perm in seen_perm:
 continue
 seen_perm.add(perm)

 print(perm)