Название этой проблемы перестановки / сортировки?

10

Вам дан массив длины . Каждый элемент массива принадлежит одному из K классов. Вы должны переставить массив, используя минимальное количество операций подкачки, чтобы все элементы одного и того же класса всегда были сгруппированы вместе, то есть они образуют непрерывный подмассив. Например: nK
Осталось еще три действительных соглашения.

[2,1,3,3,2,2][2,2,2,1,3,3], or[2,1,3,3,2,2][1,2,2,2,3,3], or[2,1,3,3,2,2][3,3,2,2,2,1].

Как эта проблема называется в литературе? Есть ли эффективный алгоритм для этого?

Марко Букал
источник
1
Я не уверен, что у этой проблемы есть имя, хотя это, безусловно, возможно. Не все мыслимые проблемы имеют имена.
Юваль
2
На практике это можно назвать группировкой . Я не знаю терминологии в классической алгоритмике. (Это, безусловно, интересная и потенциально трудная проблема! Минимизация числа перестановок создает ощущение «найди лучшую перестановку групп», что, в свою очередь, ощущается как NP-hard-ish.)
Рафаэль
Ну, ребята, спасибо вам сейчас. Конечно, я заинтересован в решении проблемы, но подумал, что она уже изучена, поэтому просил ссылку.
Марко

Ответы:

6

Примечание: это доказательство твердости, и я думаю, что существуют практические алгоритмы, такие как целочисленное программирование и т. Д.

Учитывая экземпляр BIN_PACKING , где вы хотите , чтобы упаковать число п 1 , ... , п K в L бункеров размером м 1 , ... , м L , и гарантируется , что Σ п я = Е м J = N , то мы могли бы разработать пример вашей проблемы следующим образом:Kn1,,nKLm1,,mLni=mj=N

  • Есть классов;K+(N+1)(L1)
  • Первые классов имеют размер n 1 , , n K соответственно, а каждый из остальных классов имеет размер N + 1 ;;Kn1,,nKN+1
  • Массив разбивается на слоты размером: где каждый слот размера ( N + 1 ) 2 упаковано с N + 1 классами, расположенными смежно, а остальные расположены произвольно.
    m1,(N+1)2,m2,(N+1)2,m3,,(N+1)2,mL
    (N+1)2N+1

(N+1)2N

Виллард Жан
источник
Nm1,,mL(N+1)2(N+1)N+1уже поменяется местами, поэтому мы не можем) или «сдвинуть» все это на одну позицию влево или вправо (но это влечет за собой «скольжение» каждого ...
j_random_hacker
N+1N+1N
1

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

iniijLiijinijLiiO(n)O(Kn)

  1. LiK=2K
  2. Li

В вашем примере обе эти оценки дают 1 (в последнем случае можно округлить 0,5), что, конечно, является свободным.

j_random_hacker
источник