Деление составного множества на равные части

[denny]

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

Назовем областью объединение вещественных интервалов:
$\bigcup\limits_{i=1}^{n} [a_i, b_i]$
Для простоты не будем рассматривать фракталы, бесконечные последовательности и т.д..

Задача: нужно разделить область на $M$ равных частей.
Под равенством понимается равенство мер.
Опять же для простоты мера будет классической: $|b_i-a_i|$
Выглядит это примерно так:

Серая область разделена на четыре равные по мере части, которые потом окрашены в разные цвета.



Хотtлось бы придумать красивый математически и эффективный алгоритм для такого деления.
Можно, конечно, использовать курсор, который "ползет" по области, отсчитывая меру и оставляя метки.
Более интересная идея: состыковать все интервалы влево (используя некое формализованное преобразование),
расставить метки на сплошной области, а потом применить обратное преобразование.
Я уже почти так сделал, но был бы рад услышать другие варианты!

И конечно, самое желаемое - это сделать тоже самое на окружности, т.е. по модулю 1.
Но тут я даже не знаю, как подступиться.

[Dmitriy40]

Подсчитать общую длину.
Поделить на количество частей $n$.
От начала (или любой точки любого интервала на окружности) отмерить $n$ раз полученную длину, если не влезло в один интервал, продолжить в следующем.
Профит.

[svv]

denny в сообщении #1561169 писал(а):

Для простоты не будем рассматривать фракталы, бесконечные последовательности и т.д..

Хорошо бы ещё потребовать, чтобы никакие два интервала не пересекались.
А вот сортировать список интервалов по возрастанию $a_i$ — необязательно.

[B@R5uk]

Да, если изначальное множество задано пересекающимися отрезками, то потребуется некоторая предобработка.

Кстати, требуется ли, чтобы разбиение было таково, чтобы ни одна область не перекрывалась другой? Под "перекрывается" я понимаю следующее. Если A и B — области (множества точек отрезка), то если

$$\exists\;a,\;c\in A,\;\exists\;b\in B:a\le b\le c$$

то область B перекрывается областью A. Если ответ положительный, или если требуется предобработка, то список областей придётся отсортировать.

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

Так же можно подумать над тем, чтобы при разбиении количество "рваных" областей было как можно меньше. Тут правда, всё зависит от того, каков ответ на первый мой вопрос.

[denny]

Да, вполне можно потребовать, чтобы интервалы не пересекались.
И концы могут быть рациональными.

Dmitriy40 в сообщении #1561171 писал(а):

От начала (или любой точки любого интервала на окружности) отмерить $n$ раз полученную длину, если не влезло в один интервал, продолжить в следующем.
Профит.

Это и есть пробегание курсора. Так можно, но реализация со всеми if-while получается громоздкая. Хотелось бы более математическое что-то

[svv]

denny
На Вашей картинке слева направо идёт сначала синий цвет, потом жёлтый и так далее. И пока синий "не закончится", другой цвет не начинается. Я не знаю, разрешается ли взять 10 синих, 15 жёлтых, 7 красных кусочков и так далее, которые могут чередоваться как угодно, лишь бы суммарная длина интервалов каждого цвета была одинаковой.
Если да, тогда можно просто каждый $i$-й интервал $(a_i,b_i)$ разделить на $M$ равных разноцветных кусочков длиной $(b_i-a_i)/M$.

[denny]

svv в сообщении #1561209 писал(а):

denny
На Вашей картинке слева направо идёт сначала синий цвет, потом жёлтый и так далее. И пока синий "не закончится", другой цвет не начинается. Я не знаю, разрешается ли взять 10 синих, 15 жёлтых, 7 красных кусочков и так далее, которые могут чередоваться как угодно, лишь бы суммарная длина интервалов каждого цвета была одинаковой.
Если да, тогда можно просто каждый $i$-й интервал $(a_i,b_i)$ разделить на $M$ равных разноцветных кусочков длиной $(b_i-a_i)/M$.

Да, спасибо, это интересный вариант!
На самом деле основную задачу можно назвать игра "дифференциация-интеграция".
Нечто вроде альтернативы клеточным автоматам, в которых по простым правилам могут получаться сложные структуры.
Я пытаюсь получить также достаточно простые правила деления и объединения множеств,
которые могут породить сложную структуру.
Все же деление на идущие подряд, уникальные области интуитивно проще, но ваш вариант также возможен, тем более в реализации он элементарен.

[denny]

Все же остановился на своей идее. Чисто алгоритмический подход оказался громоздким, слишком много вложенных while.
Но если у кого-то получится коротко, буду признателен за пример кода/псевдо-кода.

Еще раз сформулирую задачу. Есть конечное объединение $N$ не пересекающихся интервалов:
$\mathfrak{S}=\bigcup\limits_{i=1}^{N} [a_i, b_i]$
Нужно разделить $\mathfrak{S}$ на $M$ областей равной меры.
Пока рассматриваем интервалы на действительной оси с аддитивной мерой $\sigma_i=\lvert b_i - a_i \rvert$

Мой метод прост. Сдвигаем все интервалы влево, к первому. Запоминаем сдвиги.
Размечаем на равные части полученную связную область, и потом раздвигаем обратно.

$i\text{-тый}$ сдвиг:
$\Delta_i = b_1-b_i+\sum\limits_{1<k \leqslant i}\sigma_k$

$i\text{-тый}$ левый край после сдвига:
$a'_i=a_i + \Delta_i $

Метки, делящие на равные части "спрессованную" область меры $\Sigma$:
$\xi'_i=a_1+i\cdot\Sigma/M$

Единственный алгоритмический момент:
для каждого $\xi'_i$ нужно найти такой индекс $j(i)$, что $a'_j \leqslant \xi'_i \leqslant a'_{j+1}$

В любом языке есть простые встроенные функции для такой операции.
Найдя нужный индекс, выполняем обратное преобразование и получаем
метки в абсолютных координатах:
$\xi_i=\xi'_i-\Delta_{j(i)}$

Возможно, что все это можно еще больше упростить, но пока не вижу как.
Уверен, что такой подход можно применить и к интервалам на окружности, по модулю.

[svv]

denny в сообщении #1561250 писал(а):

Единственный алгоритмический момент:
для каждого $\xi'_i$ нужно найти такой индекс $j(i)$, что $a'_j \leqslant \xi'_i \leqslant a'_{j+1}$

Я хочу Вас уговорить на стратегическое упрощение. Идея вот в чём.

svv в сообщении #1561187 писал(а):

А вот сортировать список интервалов по возрастанию $a_i$ — необязательно.

Итак, у нас на входе алгоритма есть список интервалов, не отсортированный по возрастанию. Допустим, текущий цвет синий, мы доходим до конца интервала, а синяя краска ещё осталась. Тогда мы продолжим использовать синюю краску на другом интервале, НО не обязательно на соседнем справа интервале на числовой прямой, а просто на следующем в списке, где бы он ни находился на прямой.

Ведь совершенно не важно, в каком порядке интервалы №1,№2,№3... расположены на прямой. Лишь бы не пересекались.