Ordonner les éléments pour que certains éléments ne se rencontrent pas entre eux

Étant donné un entier et un ensemble de triplets d'entiers distincts trouver un algorithme qui trouve soit une permutation de l'ensemble telle que ou détermine correctement qu'aucune telle permutation n'existe. Moins formellement, nous voulons réorganiser les nombres de 1 à ; chaque triple dans indique que doit apparaître avant dans le nouvel ordre, mais ne doit pas apparaître entreS ⊆ { ( i , j , k ) ∣ 1 ≤ i , j , k ≤ n , i ≠ j , j ≠ k , i ≠ k } , π { 1 , 2 , … , n } ( i , j , k ) ∈ $n$

Exemple 1

Supposons que et . alorsS = { ( 1 , 2 , 3 ) , ( 2 , 3 , 4 ) $n=5$$S = \{(1,2,3), (2,3,4)\}$

• $\pi = (5, 4, 3, 2, 1)$ n'est pas une permutation valide, car , mais .π ( 1 ) > π ( 3 $(1, 2, 3)\in S$$\pi(1) > \pi(3)$

• $\pi = (1, 2, 4, 5, 3)$ n'est pas une permutation valide, car mais .π ( 1 ) < π ( 3 ) < π ( 5 $(1, 2, 3) \in S$$\pi(1) < \pi(3) < \pi(5)$

• $(2, 4, 1, 3, 5)$ est une permutation valide.

Exemple 2

Si et , il n'y a pas de permutation valide. De même, il n'y a pas de permutation valide si et ( Je pense; peut-être fait une erreur ici).S = { ( 1 , 2 , 3 ) , ( 2 , 1 , 3 ) $n=5$$S = \{(1, 2, 3), (2, 1, 3)\}$$n=5$$S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Bonus: quelles propriétés de déterminent si une solution réalisable existe?$S$

Voici un algorithme naïf. Il repose en fin de compte sur la force brute, mais peut parfois fonctionner correctement.

$(\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]$

Voici une réponse partielle:

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