Python - Conditional 2D Permutation

Question

Question:

How might it be possible to calculate the permutations on a 2D array, but such that the sum of the indicies cannot exceed a certain number?

E.g:

maxsumindex = 4
matrix = [[1,2,3], [2,3,4], [3,4,5]]

Where the permutation of matrix[0][2], matrix[1][2] and matrix[2][3] is not possible because 2+2+3 exceeds maxsumindex.

Context:

The overarching solution I'm trying to create is a way to calculate the most tax efficient allocation of personal allowance.

Let's say the maximum personal allowance is 12500. It can be allocated to any income.

To do this, I'm creating a 2D array of bands thus:

x = [[0, pa, 37500, 150000, np.inf] for pa in range(0, 12500)]
bands = np.array(x)

After calculating the taxes thus:

def VectorTaxes(income, bands, rates):
    incomes = [income]
    #2d vector clipping of incomes to the ranges. Do this for each income type and bands.
    incomes_ = np.broadcast_to(incomes, (bands.shape[0], bands.shape[1] - 1))
    amounts_in_bands = np.clip(incomes_,
                                bands[:, :-1], bands[:, 1:]) - bands[:, :-1]
    deductions = rates * amounts_in_bands
    #Final taxes in a 1d array.
    taxes = deductions.sum(axis=1)
    return taxes

tax_income1 = VectorTaxes(...)
tax_income2 = VectorTaxes(...)
tax_income3 = VectorTaxes(...)
...
tax_incomen = VectorTaxes(...)

I have a 1D array for each income taxed whose indicies correspond to the personal allowance allocated.

For two incomes, my solution would be to np.flip() the second array and find the column with the minimum sum (because the allowance is in one or the other).

However when more incomes are added it becomes extremely complex and I don't know how to handle it. I obviously can't do a min sum over the column because it would exceed the maximum personal allowance and there are so many permutations to calculate, or in other words: A permutation of tax_income1[10000] with tax_income2[2000] and tax_income3[3000] would be invalid because of the sum of the indicies exceeds the maximum personal allowance.

Manually I'd do it something like:

1. Try a 2500 allowance for income one.
2. 5000 allowance for income two.
3. 2500 allowance for income three.
4. 2500 allowance for income four.
5. Record the sum.
6. Try again with different permutations.

I have absolutely no idea how to do this in an efficient way!

How would it be best to proceed?