Уточнение разбиения

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

• Упорядоченная последовательность множеств в семействе в такой форме, как двусвязный список, который позволяет вставлять новые наборы в середину последовательности.
• Соответствующая каждому множеству i коллекция его элементов, организованная как двусвязный список или массив, чтобы обеспечить возможность быстрого удаления отдельных элементов из коллекции. Альтернативно этот компонент структуры данных может быть представлен путем хранения всех элементов всех множеств в одном массиве, отсортированном по идентификатору множества каждого элемента, или путем представления коллекции элементов в любом множестве _i по его начальной и конечной позициям в этом массиве.
• С каждым элементом связан набор, к которому он принадлежит.

Уточнение разбиения также является ключевым этапом в лексикографическом поиске