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

Question

Учитывая список элементов l размера n и заданный предикат succeeds(i1,i2), который возвращает true, если i2 следует i1, каков наилучший алгоритм для перестановки элементов l таким образом, чтобы для всех элементов il, succeeds(i,i.next) возвращает true?

Answer 1

Если нет никаких ограничений на то, каким может быть отношение преуспевания (то есть оно не должно быть транзитивным, рефлексивным, симметричным и т. Д.), То я думаю, что эта проблема является NP-трудной из-за сокращения от NP-hard Гамильтонова задача о пути . Сокращение на самом деле довольно просто: с учетом графа G создайте массив узлов в графе с отношениями преуспевания, так что v преуспевает, если в исходном графе есть ребро от u до v. При такой настройке поиск способа упорядочить элементы массива (узлы) по отношениям преуспевания (соединяющим их ребрам) эквивалентен нахождению гамильтонова пути в исходном графе, поскольку каждый узел посещается ровно один раз. Следовательно, вы вряд ли найдете эффективный алгоритм для этого, если P = NP.

Извините за отрицательный результат, и надеюсь, что это поможет!

Answer 2

Если только один элемент может следовать за каждым элементом , то эта проблема разрешима в квадратичном времени.

Это фактически имитирует создание связанного списка из данных и возвращение его в виде массива. Узкое место находит для каждого элемента - какой элемент следует за ним.

Псевдо-код:

specialSort(array,n)
   create an array a of size n
   for each i from 0 to n:
      find j such that succeeds(array[i],array[j]) == true //this may require linear search, so it is O(n)
      if there is such j:
          a[i] = j
      else:
          a[i] = -1
   end for
   find i such that for any j: a[j] != i
   create empty result array of size n
   j = 0;
   while (i != -1):
      result[j++] = array[i]
      i = a[i]
   end while
   return result

Если нет ограничений на число элементов, которые могут следовать за каждым элементом, то ответ @templatrtypedef дал вам правильный ответ, и ваша задача эквивалентна поиску гамильтонова пути.

РЕДАКТИРОВАТЬ: проблема разрешима для любого хорошо упорядоченного отношения :
Обратите внимание, что если для каждого элемента может быть более одного преемника, но отношение succeed() хорошо упорядочено [без «петель»], то вы можете построить DAG из этой задачи [каждый Элемент является вершиной, и для каждой пары есть ребро, такое, что succeed(a,b) == true], используйте топологическое упорядочение - и возвращайте его.
Это также квадратичное время, с другой стороны - горлышко бутылки находит края.