Is there a way to change this nested loop into a recursive loop?

Question

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

Answer 1

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)

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