dsharlet / array

C++ multidimensional arrays in the spirit of the STL
Apache License 2.0
198 stars 15 forks source link

Implement `shape::is_one_to_one` and `shape::is_subset_of` #2

Open dsharlet opened 4 years ago

dsharlet commented 4 years ago

In order to determine if a shape maps two different indices to the same flat indices (i.e. is_one_to_one is false), we need to solve:

x_0*S_0 + x_1*S_1 + x_2*S_2 + ... == y_0*S_0 + y_1*S_1 + y_2*S_2 + ...

where x_i, y_i are (different) indices, and S_i are the strides of this shape. This is equivalent to:

(x_0 - y_0)*S_0 + (x_1 - y_1)*S_1 + ... == 0

We don't actually care what x_i and y_i are, so this is equivalent to:

x_0*S_0 + x_1*S_1 + x_2*S_2 + ... == 0

where x_i != 0. This is a linear diophantine equation, and we already have one solution at x_i = 0, so we just need to find other solutions, and check that they are in range.

This is pretty hard. Wikipedia research so far suggests we need to rewrite the equation as a system of linear diophantine equations, and then use the "Hermite normal form" to get the unbounded solutions, and then do some combinatoric search for the in-bounds solutions. This is an NP-hard problem, but the size of the problems are small, and I don't think these functions need to be fast.

is_subset_of is possibly similar.

dsharlet commented 4 years ago

is_subset_of needs to possibly handle even shapes of different rank, but it boils down to solving a problem of the same form.