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

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. Также отсортировано.

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

EDIT:

mweerden:

Мне не ясно, каковы точные условия отображения. Почему точно не разрешается просто производить перестановку [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) п))