Insertion efficace dans la liste en gardant un nombre minimal d'inversions

Supposons deux listes d'éléments comparables: u et s. Soit INV (u) le nombre d'inversions dans u.

Je recherche un algorithme efficace pour insérer les éléments de s dans u avec une augmentation minimale de INV (u).

Fondamentalement, je voudrais insérer des objets dans une liste tout en la gardant "aussi triée que possible" tout en gardant l'ordre de la première liste.

Exemple:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

Comme vous pouvez le voir, il n'y a pas de solution optimale unique.

Je serais heureux de toute idée ou direction à examiner.

Ceci est une élaboration sur la réponse de Trevore. Il est trop long pour tenir dans un commentaire et contient les preuves de sa solution (ou du moins comment je la comprends).

Vous pouvez montrer que dans toute solution optimale, les éléments de apparaîtront ordonnés. $s$Sinon, supposez et ils apparaissent dans l'ordre inverse dans une solution optimale. Soit le nombre d'éléments entre et qui sont inférieurs à et le nombre de ceux qui sont plus grands que . Définissez et même manière pour . Notez que et . Permutation etσ 1 s 1 s 2 s 1 β 1 s 1 σ 2 β 2 s 2 σ 1 ≤ σ 2 β 2 ≤ β 1 s 1 s 2 - β 1 + β 2 - σ 2 + σ 1 - $s_1 < s_2$$\sigma_1$$s_1$$s_2$$s_1$$\beta_1$$s_1$$\sigma_2$$\beta_2$$s_2$$\sigma_1 \leq \sigma_2$$\beta_2 \leq \beta_1$$s_1$$s_2$changera le nombre d'inversions de qui est au plus -1.$-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$

Il n'est pas difficile de voir que les éléments de peuvent être insérés indépendamment. $s$Puisqu'ils paraissent ordonnés, les éléments de ne se «sentent» pas mutuellement. Autrement dit, les paires d'éléments de ne contribuent pas au nombre d'inversion. Pour ce faire, insérez la médiane de manière optimale dans le temps linéaire. Ensuite, récursivement, insérez des éléments de inférieurs à la médiane à gauche de la médiane et des éléments plus grands que la médiane à sa droite.s s $s$$s$$s$$s$

Soit la médiane insérée en position , le temps d'exécution de ceci satisfait,, le linéairefacteur est de trouver la médiane et traînant les éléments de . Il est facile de montrer par induction que .T ( | s | , | u | ) = T ( | s | / 2 , | u | - k ) + T ( | s | / 2 , k ) + | u | + | s | | s | s T ( | s | , | u | ) = $k$$T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$$|s|$$s$$T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$

Notez que la dépendance deici est optimal. Puisque résoudre le problème avec vide équivaut à trier utilisant uniquement des comparaisons. La dépendance deest également optimale, puisque le problème pour une liste singleton et une liste doit exiger un travail linéaire.u s | u | s $|s|$$u$$s$$|u|$$s$$u$

Ok, voici ma solution:

Une observation (que j'ai plus ou moins prouvée) est qu'une solution optimale sera toujours celle dans laquelle s est trié en ordre croissant. Cela donne lieu à un algorithme O ((| u | + | s |) * log (| s |)).

Pour trouver la solution optimale pour un seul élément, faites comme je l'ai dit dans mon commentaire: prenez un élément de s, comparez-le à chaque élément de u de gauche à droite, incrémentez un compteur est une inversion et reportez le nombre précédemment calculé. Parcourez ensuite la liste de droite à gauche avec le même élément, en augmentant le nombre pour chaque position.

C'est O (| u |).

Trier s.

Pour l'élément central de s à la position m: Trouvez la meilleure position b dans u (en utilisant la méthode ci-dessus).

Divisez s en m et u en b et appelez récursivement avec les parties gauche et droite, concaténant les résultats avec m dans le bon ordre.

Arrêtez dès que u ou s sont vides.