Блог

Необходимо разделить массив данных, состоящий из n строк и m столбцов, на s непересекающихся частей (приблизительно) одинакового размера.

Реально n * m не обязательно делится на s, поэтому нам приходится работать с блоками размером floor(n * m) и ceil (n * m). Однако на данный момент это наименьшая из моих проблем.

Основное требуемое свойство заключается в том, что каждый блок структурно отделен от целостности данных в том смысле, что ни большие куски глобально смежных элементов не принадлежат одному и тому же блоку, ни это разделение в стиле шахматной доски.

Что бы вы предложили? Должен ли я просто обратиться к случайности или есть какие-то аккуратные структуры, подходящие в этой ситуации?

Я обнаружил, что лениво обдумываю это во время кратковременных периодов простоя, и кажется, что должно быть несколько способов сделать это; это несколько зависит от того, чего вы хотите достичь. Вот о чем я мечтал, на случай, если это полезно.

Насколько я понимаю, вы хотели бы разделить массив n x m на i примерно равных частей, где n и m неизвестны, и без каких-либо смежных элементов, разделяющих набор.

Во-первых, теорема о четырех цветах говорит нам, что вы можете сделать это с четырьмя наборами; возможно, стоит посмотреть, существует ли существующий алгоритм для их обработки для массива. С другой стороны, вы можете тривиально сделать это для n x m групп, присвоив каждому элементу его собственный одноэлементный набор.

То, как вы подходите к этому, скорее зависит от того, что вы хотели бы минимизировать — хотите ли вы наименьшее количество групп i, например. Если бы это не было проблемой, вы могли бы попробовать что-то вроде следующего:

Рассматривая только n, если n четно, разделите массив на наборы размером n / 2, затем создайте n / 2 наборов — один, содержащий 1-й элемент каждой группы, один, содержащий 2-й и т.д. Они будут содержать только непоследовательные элементы. Если n нечетное, создайте одноэлементный набор, состоящий из n-го элемента, а затем выполните описанные выше действия с остатком.

В одномерном случае это даст вам n / 2 наборов размером 2 с потенциальным дополнительным набором размером 1. Он также будет работать с 2 измерениями, разделяя как n, так и m, как указано выше.

Как уже было сказано, это, вероятно, не тот ответ, который вы искали, но я надеюсь, что это может помочь в дальнейшем расследовании — вы могли бы заменить проверку нечетности / четности на единицу, например, для наибольшего общего множителя или простого разложения. Возможно, также стоит спросить об этом в Math Overflow .

Я могу написать некоторый псевдокод (или какой-нибудь python) относительно того, как это может быть возможно, если это будет полезно.