Уменьшить перестановку

Question

Мне нужен алгоритм, который может сопоставить серии перестановок с одним числом, а также уменьшить последующие числа.

Таким образом, серия — это последовательный набор чисел в перестановке, отсортированный и упорядоченный.В списке 1;2;3;5;6;4 есть два прогона: 1;2;3 и 5;6.Я хочу заменить их одним числом, минимум, поэтому, если после удаления серий у нас есть перестановка из 4 элементов, в перестановке используются числа 1...4.В приведенном выше примере нам нужно сократить два прогона.первый прогон будет равен 1, 4 преобразуется в 2, а [5;6] преобразуется в 3, чтобы сохранить второй критерий.Если я отсортирую уменьшенную перестановку, затем разверну элементы внутри отображения и отсортирую исходную перестановку, я получу тот же результат.В результирующей перестановке не должно быть никаких пробегов.

Например (я выделил прогоны):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

пока прохожу по списку и составляю список списков, группируя прогоны.На самом деле вторая часть — самая сложная часть в создании чистого решения.Я подумал о наивном подходе, любопытно, есть ли у кого-нибудь какой-нибудь хитрый трюк, который может сделать это лучше, чем мой, я примерно в O (2n + n log n),

• замена прогонов головным элементом прогона и вставка этих данных в хеш-таблицу (для возможности восстановления)
• сортировка для создания карты недостающих цифр с отсортированным индексом.[1;6;5;4] выведет [(1,1);(4,2);(5,3);(6,4)]
• замена списка на шаге 1 картой, созданной на шаге 2, и обновление хеш-таблицы для перевода.

еще раз пробежимся по примеру:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Если я отсортирую эту перестановку и реконструирую:[1;2;3;4], 3->3;4 и 4->5;6 я получаю, 1;2;3;4;5;6.Также отсортировано.

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

РЕДАКТИРОВАТЬ:

мвеерден:

Мне неясно, каковы точные условия отображения.Почему именно нельзя просто создать перестановку [1,2,...,N] для перестановки с N пробегами?Кажется, вы предпочитаете сопоставлять прогон с числом из этого прогона, но (поскольку это не всегда возможно), вы, кажется, допускаете некоторую свободу.–

Я не предпочитаю сопоставлять прогон числу внутри этого прогона (см. выше!), но мне нужно сохранить заказ.Перестановка [1;2;3...N] является пробега и, таким образом, может быть сокращен еще больше.Именно поэтому оно недействительно.Порядок будет иметь значение в дальнейших операциях в другом алгоритме, но в конце отдельные элементы можно расширить, чтобы сохранить исходную перестановку.

Answer 1

Обозначение:

• счет начинается с 1
• l.i это элемент i списка l
• l+m это объединение списков l и m
• прогон — это максимальный подсписок, который является списком [n,n+1,n+2,...,m] для некоторых n и m с n <= m

Итак, нам дана перестановка p из списка [1,2,...,N].Мы разделяем p в бегах r_1,r_2,...,r_M такой, что p = r_1+r_2+...+r_M.Затем мы ищем перестановку q из [1,2,...,M] такой, что r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

Например, если p = [1,3,4,2,5,6], у нас есть N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] и r_4 = [5,6].В этом случае нам понадобится q быть [1,3,2,4] как r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

Обратите внимание, что q не может содержать серии длиной более одной на определение;если бы это было так, то есть i < M с q.i + 1 = q.(i+1) и, следовательно, подсписок r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) из [1,2,...,N], но r_(q.i)+r_(q.i + 1) также является подсписком p что противоречит этому r_(q.i) и r_(q.i + 1) являются пробежками.

Теперь, чтобы найти q учитывая p, мы предполагаем наличие структуры данных отображения с O(1) вставки и поиск чисел и списков с O(1) добавляет и прямой обход.Затем делаем следующее.

• Сначала мы создаем список runheads = [r_1.1,r_2.1,...,r_M.1].Это можно сделать тривиально, пройдя p сохраняя при этом текущий пробег.На этом этапе мы также запоминаем максимальное число, с которым можно получить N в конце и построим отображение heads с элементами runheads как ключи.Этот шаг явно O(n).Обратите внимание, что не имеет значения, какие значения heads есть, поэтому мы можем просто использовать run r_i как значение ключа r_i.1.

• Далее мы итерируем от 1 до (и включая) N поддержание ценности k с начальной стоимостью 1.Для каждого значения i мы проверяем, если i в heads.Если это так, мы добавляем i -> k к отображению f и увеличить k.Этот шаг также явно O(n).Чтобы иметь возможность вернуться из q к p мы также можем сохранить дополнительное отображение rev с k -> i или даже k -> runheads(i) без каких-либо дополнительных затрат.

• Наконец, мы применяем отображение f к элементам runheads получить q.Снова O(n).

Для иллюстрации примера рассмотрим случай, когда p = [1,3,4,2,5,6].

• На первом этапе мы получаем runheads = [1,3,2,5], N=6 и heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

• Для второго шага у нас есть четыре случая, для которых нам нужно что-то сделать: 1, 2, 3 и 5.Для этих случаев у нас есть значения для k которые 1, 2, 3 и 4, соответственно.Это значит, что f будет { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }.(И rev было бы { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } или { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, в зависимости от того, что вы решили сохранить.)

• Получить q мы рассчитываем map(f,runheads) который [f(1),f(3),f(2),f(5)] или, что то же самое, [1,3,2,4].

Итак, если я не ошибся и если структуры данных удовлетворяют вышеуказанным требованиям, то это решение должно быть O(n).Обратите внимание, что на практике может оказаться более полезным использовать свои собственные (O(n*log(n))) решение.Если у вас большой p но всего за пару прогонов, сортировка runheads и использование этого для построения сопоставлений может быть более эффективным.Я думаю, что p чтобы это произошло, должно быть довольно большим.

Answer 2

Отредактировано для пояснения

шаг 1:Запустите алгоритм, но вместо создания только одной хеш-таблицы создайте хеш-таблицу (D1), индексированную по заголовку набора, с которым она сопоставляется (например, для [3,4] это будет 3) и список (L1). с самим набором

[3;4;6;8;1;2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Шаг 2:Если вы посмотрите на коллекции, которые у нас сейчас есть, вы увидите, что для данного набора у нас есть индекс, в котором мы его нашли (в L1), и значение Head.Правильным значением карты будет минимальное целое число между ними, которое еще не занято.Например, для [3,4] значение должно быть между 1 и 3, а поскольку 1 уже занято, соответствующее значение равно 2.Учтите, что, поскольку D1 индексируется по значению Head, всегда будут приниматься более низкие значения, если соответствующий набор существует.В этом примере [1,2] отображается в 1, так что этот ключ уже «занят».Итак, в псевдокоде:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Например

• мы берем первое значение в L1 -> [3,4]...
• получить голову = 3
• Начиная с 1, мы ищем D1[1], который уже занят, поэтому увеличиваем до 2.
• Мы ищем пустой D1[2], поэтому присваиваем D1[2] = [3,4] и удаляем D[3]

Это дает не O(n), а что-то вроде O(n+log(n)) (n для первого шага, log(n) для второго)

Для примера выше, который вас поймет:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Теперь, если у вас есть [3;4;8;6;1;2], это приведет к

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

поскольку он использует абсолютный порядок в исходном массиве, я не знаю, все ли в порядке, или вы захотите, чтобы 6 было в индексе 3, а 8 - в индексе 4, в этом случае вам, вероятно, придется предварительно заказать L1 на основе головы, которая увеличит вашу сложность на Log (n)

Если вам нужно сделать предзаказ, у вас будет 0(n+log^2(n)), что не так уж плохо (может быть, и меньше, если предположить, что QuickSort имеет O(Log n), порядок L1 будет O(log(log n))