Сортировка, упаковка и переназначение массива индексированных значений для минимизации перекрытия

Question

Sitation:

обзор:

У меня есть что-то вроде этого:

std::vector<SomeType> values;
std::vector<int> indexes;

struct Range{
    int firstElement;//first element to be used in indexes array
    int numElements;//number of element to be used from indexed array
    int minIndex;/*minimum index encountered between firstElement 
        and firstElements+numElements*/
    int maxIndex;/*maximum index encountered between firstElement 
        and firstElements+numElements*/
    Range()
        :firstElement(0), numElements(0), minIndex(0), maxIndex(0){
    }
}

std::vector<Range> ranges;

Мне нужно отсортировать значения, индексы переназначения иПересчитать диапазоны, чтобы минимизировать maxValueIndex-minValueIndex для каждого диапазона.

детали:

значения - это массив (хорошо, «вектор») некоторыхтип (не имеет значения, какой).элементы в значениях могут быть уникальными, но это не гарантируется.

indexes - вектор целых чисел.каждый элемент в «indexes» является индексом, который соответствует некоторому элементу в значениях .Элементы в индексах не являются уникальными, одно значение может повторять несколько типов.И indexes.size ()> = values.size ().

Теперь диапазоны соответствуют «фрагменту» данных из indexes .firstElement - это индекс элемента, который будет использоваться из indexes (т. е. используется следующим образом: indexes [range.firstElement]), numElements - это (очевидно) количество элементов, которые нужно использовать, minIndex - это mininum in (indexes [firstElement] ... indexes [firstElement + numElements-1]) a, d maxIndex максимально в (indexes [firstElement] ... indexes [firstElement + numElements-1]).Диапазоны никогда не пересекаются.Т.е. для каждых двух диапазонов a, b

((a.firstElement >= b.firstElement) && (a.firstElement < (b.firstElement+b.numElements)) == false

Очевидно, что когда я делаю какую-либо операцию с значениями (переключение на элементы и т. Д.), Мне нужно обновить индексы (чтобы они продолжали указыватьна то же значение) и пересчитать соответствующий диапазон, чтобы значения minIndex и maxIndex были правильными.

Теперь мне нужно переставить значения таким образом, чтобы минимизировать Range.maxIndex - Range.minIndex.Мне не нужен «лучший» результат после упаковки, достаточно «вероятно, лучшей» или «хорошей» упаковки.

проблема:
Переназначение индексов и пересчет диапазоновлегко.Проблема в том, что я не уверен, как сортировать элементы в значениях , потому что один и тот же индекс может встречаться в нескольких диапазонах.

Есть идеи о том, как действовать?* ограничения:

Изменение типа контейнера не допускается.Контейнеры должны быть похожи на массивы.Нет карт, нет списков.Но вы можете свободно использовать любой контейнер, который вы хотите во время сортировки.Кроме того, нет ни буста, ни внешних библиотек - чистый C ++ / STL, мне действительно нужен только алгоритм.

дополнительная информация:

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

Цель алгоритма - убедиться, что выходные данные

for (int i = 0; i < indexes.size; i++){ 
    print(values[indexes[i]]); //hypothetical print function
}

будут одинаковыми до и после сортировки, атакже убедившись, что для каждого диапазона Range.maxIndex-Range.minIndex (после сортировки) настолько мал, насколько это возможно, при разумных усилиях.Я не ищу «идеальное» или «наиболее оптимальное» решение, достаточно иметь «вероятно идеальное» или «возможно, наиболее оптимальное» решение.

PS Это НЕ домашнее задание.

Answer 1

Это не алгоритм, просто мысли вслух.Вероятно, он сломается, если будет слишком много дубликатов.

Если дубликатов не было, вы просто переставите значения так, чтобы индексы были 0,1,2, и так далее.Итак, для начала давайте исключим значения, которые имеют двойные ссылки, и расположим остальные

Поскольку имеются дубликаты, вам необходимо выяснить, где их можно прикрепить.Предположим, что на дубликат ссылаются диапазоны r1, r2, r3.Теперь, пока вы вставляете дубликат между min ([r1, r2, r3] .minIndex) -1 и max ([r1, r2, r3] .maxIndex) +1, сумма maxIndex-minIndex будет одинаковойне важно, куда вы его вставите.Перемещение точки вставки влево уменьшит значение max-min для всех диапазонов влево, но увеличит его для всех диапазонов вправо.Таким образом, я думаю, что разумно сделать вставку дубликата по левому краю (minindex) самого правого диапазона (с наибольшим minIndex) r1, r2, r3.Повторите со всеми дубликатами.

Answer 2

Хорошо, похоже, есть только один способ надежно решить эту проблему:

Убедитесь, что ни один индекс не используется одновременно двумя диапазонами, дублируя значения. Я сканирую весь массив индексов, и когда вы обнаруживаете индекс (значения), который используется более чем в одном диапазоне, вы добавляете копию этого значения для каждого диапазона - каждый с уникальным индексом. После того, как эта проблема становится тривиальной - вы просто сортируете значения таким образом, чтобы убедиться, что массив values ​​ сначала содержит значения, используемые только первым диапазоном, затем значения для 2-го диапазона и так далее. То есть это получит максимальную упаковку.

Поскольку в моем приложении более важно минимизировать сумму (диапазоны [i] .maxIndex-range [i] .minIndex), чтобы минимизировать количество значений, этот подход работает для меня.

Я не думаю, что есть другой надежный способ решения проблемы - довольно легко получить ситуацию, когда индексы используются каждым диапазоном, и в этом случае не будет возможности «упаковать» данные независимо от того, что ты делаешь. Даже если индекс будет использоваться одновременно двумя диапазонами, это приведет к проблемам - вы можете получить диапазоны a, b и c, где a и b, b и c, a и c будут иметь общие индексы. В этом случае также будет невозможно упаковать данные.