Эталонная реализация конкретного алгоритма «разделяй и властвуй», который находит границу Парето

Question

Для любой коллекции частично упорядочиваемых элементов можно взять максимум указанной коллекции как все элементы, которые не меньше любого другого элемента в коллекции. Особый случай возникает, когда эта коллекция представляет собой набор n-мерных векторов (в Rust мы могли бы иметь что-то вроде (D1,D2,D3,...,Dn) как тип n-мерных векторов и Vec<(D1,D2,D3,...,Dn)> будет типом коллекций n-мерных векторов), где каждое измерение Di полностью упорядочен, а частичный порядок определяется как (a1,a2,a3,...,an)<=(b1,b2,b3,...,bn) если только (a1<=b1) && (a2<=b2) && (a3<=b3) && ... && (an<=bn). Максимумы в этом случае хорошо известны в нескольких областях, поскольку это граница Парето, если измерения интерпретируются как цели, которые необходимо оптимизировать, и это результат запроса горизонта, если измерения интерпретируются как столбцы таблицы.

В Bentley80 и нескольких других статьях описан эффективный алгоритм нахождения этих максимумов. Это мое текущее понимание того, как это выглядит (так что прочтите исходное описание, так как оно исходит от человека, который на самом деле не знает, как это работает!):

---

Аргументы: Сборник V:Vec<(D1,D2,D3,...,Dn)> where D1,D2,D3,...,Dn:Ord векторов, отсортированных по первому измерению, и число n>=3 размеров.

Результат: коллекция с максимальным размером.

Шаги:

1. Если коллекция содержит только один вектор или пуста, все готово; M=V. В противном случае переходите к шагу 2.
2. Выберите медианное значение V поперек и разделите коллекцию пополам со всеми векторами, составляющие которых меньше медианы, а остальные - в.
3. Рекурсивно вычислить максимумы и, получив и соответственно.
4. Если n == 3, перебрать M_1.append(M_2)вместе, начиная с вектора с наибольшим компонентом и заканчивая наименьшим. Для каждого вектора в этой итерации, если он есть, вставьте его и запишите его компонент, если он самый большой из наблюдаемых. Иначе, vв ; вставьте его, если его составляющая не меньше наблюдаемой для векторов записи. После завершения итерации мы тоже; результат M.
5. Если n > 3, рекурсивно вычислить максимумы M1.append(M2), но с учетом самого большого измерения и отслеживания того, какие векторы были, а какие - внутри.

---

К сожалению, мне не удалось это реализовать самостоятельно. И поэтому я спрашиваю StackOverflow: может ли кто-нибудь предоставить простую и понятную реализацию алгоритма?Никакого специального языка программирования не требуется, на самом деле псевдокод также может быть наиболее очевидным выбором в этом случае, но я должен попросить не опускать детали. На мой взгляд, для этого будет полезен системный язык, такой как C или Rust.

Я, конечно, пытался сделать это сам (в Rust), но было несколько вещей, которые меня сбили с толку:

• а. Как эффективно разделить коллекцию пополам? В стандартной библиотеке Rust есть метод поиска медианы, но он нестабилен (в смысле сортировки), и мы не можем использовать его напрямую, потому что нам нужно сохранить порядок. Можно потратить кучу места / выделений, чтобы сделать это в любом случае (клонировать коллекцию, вызвать метод стандартной библиотеки для клона и найти медиану, затем выполнить итерацию по исходному вектору, проталкивая элементы, компоненты которых меньше медианы, в V1 и более крупные в V2), но мне интересно, нет ли лучшего способа.
• б. Повторяющиеся элементы сложны. В частности, в двух местах: на шаге 2, если у медианы много повторов, остается вопрос, нужно ли уделять особое внимание тому, куда их помещать (имеет ли значение количество немедианных элементов?), Что может даже выродиться в ситуация, когда все элементы равны медиане, а это означает, что нужен специальный шаг, чтобы просто пропустить это измерение, когда это произойдет. И на шаге 4 может быть много векторов с одним и тем же компонентом в обоих и в одно и то же время. Я думаю , что в этом случае нужно сделать так, чтобы алгоритм перебирал все элементы с этим D1 компонент, отслеживайте наивысшую запись, достигнутую векторами, и только затем решайте, попадают ли какие-либо векторы в разрез.
• c. Вы могли заметить, что в шаге 5 упоминается отслеживание того, какие векторы берут начало, а какие -, но никакие другие шаги не используют эту информацию. Оказывается, я тоже не знаю, что происходит. То есть, я прочитал газету, я "понял"; потому что векторы имеют строго больший Dn компонент, чем любые векторы, это означает, что в рекурсивном вызове, где мы в противном случае принимаем во внимание только размеры, мы также должны отслеживать, откуда берутся векторы, так что всякий раз, когда v2 <= v1 когда и рассматриваются как n - 1-мерные векторы, но произошли и произошли, мы знаем, что v1 а также v2на самом деле несравнимы. Но мы не сравниваем векторы прямо в алгоритме! Фактические сравнения (между D2компоненты векторов) выполняются на шаге 4, и в этот момент мы настолько удалены от других измерений, что я понятия не имею, как интегрировать информацию, которая поступает от них, в шаг. Мое лучшее предположение - «дополнить» каждый вектор дополнительным вектором битов, по одному биту для каждого измерения, чтобы перед каждой рекурсией уменьшения размерности один проходил через каждый вектор в M1 а также M2, перевернув соответствующий бит, но что потом? В итерационной части шага 4, я думаю, вам нужно отслеживать весь вектор D_2записи? Я практически прекратил свою попытку на этом этапе.