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

Дано целое число и множество триплетов различных целых чисел найдите алгоритм, который либо находит перестановку множества такую, что или правильно определяет, что такой перестановки не существует. Менее формально мы хотим изменить порядок номеров от 1 до ; каждая тройка в указывает, что должен появляться перед в новом порядке, но не должен появляться между$n$

Пример 1

Предположим, что и . затем$n=5$$S = \{(1,2,3), (2,3,4)\}$

• $\pi = (5, 4, 3, 2, 1)$ является не допустимым перестановок, так , а .$(1, 2, 3)\in S$$\pi(1) > \pi(3)$

• $\pi = (1, 2, 4, 5, 3)$ является не допустимым перестановок, так , а .$(1, 2, 3) \in S$$\pi(1) < \pi(3) < \pi(5)$

• $(2, 4, 1, 3, 5)$ является допустимой перестановкой.

Пример 2

Если и , допустимая перестановка отсутствует. Точно так же нет действительной перестановки, если и ( Я думаю, возможно, сделал ошибку здесь).$n=5$$S = \{(1, 2, 3), (2, 1, 3)\}$$n=5$$S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Бонус: Какие свойства определяют, существует ли возможное решение?$S$

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

Каждое ограничение состоит из двух конъюнктов; давайте назовем их тип- , , и тип- , . Каждый тип -$(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$$A$$i < k$$B$$\neg(i < j < k)$$B$$i>j \vee j>k$$i\neq j,j\neq k$

1. $A$$\Theta$$O(|S|)$
2. $B$$\Theta$$\Theta$$B$$\Theta$$O(|S|^2)$
3. $B$$\Theta$$|S|$
   $B$
4. $A$$B$

$n$$x_i$$[0,n-1]$

Вот частичный ответ:

$i \lt k$$NP$$i \lt k$