Find cartesians for matrix elements

[wolle]

But the problem is that the algorithm is unknown to me yet.
I thought that it's maybe known to some of you.

You can always apply exhaustive combinatorics:

1. Systematically generate all Cartesian matrixes that may occur in any matrix the size of the input matrix. Select those that are present in the input matrix.

2. Systematically generate all possible combinations of the Cartesian matrixes selected in 1. Select the valid combinations, that is where the sum of the Cartesian matrixes without overlapping matches the input matrix exactly.

3. Out of all valid combinations found in 2, select the combination(s) with the fewest Cartesian matrixes. That's it!

There are 2^(n+m) possible Cartesian matrices in an n*m input matrix, so step 1 is only feasible for small matrixes. The feasibility of step 2 depends on how many Cartesian matrixes there actually are in the input matrix. If there are k, there will be 2^k possible combinations, so also the number of combinations becomes intractable very fast. But still, this algorithm will work, and that's better than having nothing.

Both steps 1 and 2 involves generating the powerset of a set,

https://en.wikipedia.org/wiki/Power_set

Good luck!